查看: 2909|回复: 6
收起左侧

[Leetcode] Find Minimum in Rotated Sorted Array找不出问题

|只看干货
415044809 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (18)
 
 
5% (1)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本人编程小白,今天试了第一个题 (Find Minimum in Rotated Sorted Array)就蛋疼了。我编的程序在自己的codeblock下能跑对数,在网上测出的答案怎么和我私下跑的结果不一样呢?
第一题这么简单,我就是先遍历一遍找到最小的,然后把vector元素来回捣一捣。
所以我感觉是不是犯了什么编程新手的错误,所以还望大神们指点。。!!

我的代码:

class Solution {
public:
    int findMin(vector<int> &num) {
        int label = 0;                        % find the minimum
        int atom = num[label];
        for (int i = 1; i != num.size(); i++){
            if(num < atom){
                atom = num;
                label = i;
            }
        }
       vector<int> porter(num.size() - label);     % copy second part to a new vector
       for (int i = 0; i != porter.size(); i++){
            porter = num[i + label];
        }
        for (int i = num.size() - 1; i >= porter.size(); i--){     % move first part backward
            num = num[i-porter.size()];
        }
        for (int i = 0; i != porter.size(); i++){                 % copy back
            num = porter;
        }
    }
};



上一篇:一个类里面什么时候用private,什么时候用public?
下一篇:找一个二叉树上某两个节点的共同祖先,不得使用额外的数据结构,二叉树不一定是BST
Interviwer 2014-10-18 13:10:25 | 显示全部楼层

log n 算法

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (41)
 
 
0% (0)    👎
本帖最后由 Interviwer 于 2014-10-18 13:15 编辑
  1. class Solution {
  2. public:
  3.     int findMin(vector<int> &num) {
  4.         int start = 0;
  5.         int end = num.size()-1;
  6.         
  7.         if(num[start] < num[end]) {
  8.             return num[start];
  9.         }
  10.         
  11.         while(start + 1 < end) {
  12.             int mid = start + (end-start)/2;
  13.             if(num[mid] > num[end]) {
  14.                 start = mid;
  15.             }else {
  16.                 end = mid;
  17.             }
  18.         }
  19.         return min(num[start], num[end]);
  20.     }
  21. };
复制代码

评分

参与人数 1大米 +5 收起 理由
415044809 + 5 谢谢你的介绍!

查看全部评分

回复

使用道具 举报

 楼主| 415044809 2014-10-18 14:18:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (18)
 
 
5% (1)    👎
大神,看不太懂啊,能稍微说一说思路吗?我把代码copy上,竟然通过啦!
你用二分查找法应该是用到数组之前是排好序的,但咋利用呢?我也就只能理解这一点。
程序里没见你改变vector元素的值啊?咋就把元素重新排序了呢?

回复

使用道具 举报

Interviwer 2014-10-18 15:25:26 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (41)
 
 
0% (0)    👎
415044809 发表于 2014-10-18 14:18
大神,看不太懂啊,能稍微说一说思路吗?我把代码copy上,竟然通过啦!
你用二分查找法应该是用到数组之前 ...

这种题只能是log N 的算法,如果是N,面试肯定过不了, 确实是二分法,你看看后面有一道 Search in Rotated Sorted Array

这个讲的比较具体
http://www.cnblogs.com/lichen782 ... d_Sorted_Array.html

评分

参与人数 1大米 +5 收起 理由
415044809 + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

kinslover 2014-10-18 23:02:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (71)
 
 
2% (2)    👎
415044809 发表于 2014-10-18 14:18
大神,看不太懂啊,能稍微说一说思路吗?我把代码copy上,竟然通过啦!
你用二分查找法应该是用到数组之前 ...

自己写一个3个数的小例子,按照算法流程在纸上模拟一遍。然后再写一个4个数的小例子,按照算法流程模拟一遍。再写一个5个数的小例子。

之后你就基本明白了

评分

参与人数 1大米 +5 收起 理由
415044809 + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

 楼主| 415044809 2014-10-19 02:12:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (18)
 
 
5% (1)    👎
搞出来啦,谢谢大家!
回复

使用道具 举报

xixihaha2014 2014-10-19 17:26:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
  1. class Solution {
  2. public:
  3.     int findMin(vector<int> &num) {
  4.         int i = 0, j = num.size() - 1;
  5.         
  6.         while(i < j) {
  7.             if(num[i] < num[j]) {
  8.                 return num[i];
  9.             }
  10.             int m = (i + j) / 2;
  11.             if(num[m] >= num[i]) {
  12.                 i = m + 1;
  13.             } else {
  14.                 j = m;
  15.             }
  16.         }
  17.         
  18.         return num[i];
  19.     }
  20. };
复制代码
详细解释参考:[url= http://orzorz.me/learn/lesson.htm?lessonId=106]Find Minimum in Rotated Sorted Array[/url]
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表