一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1920|回复: 6
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
415044809 发表于 2014-10-18 12:13:35 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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;
        }
    }
};


Interviwer 发表于 2014-10-18 13:10:25 | 显示全部楼层

log n 算法

本帖最后由 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

查看全部评分

回复 支持 反对

使用道具 举报

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

回复 支持 反对

使用道具 举报

Interviwer 发表于 2014-10-18 15:25:26 | 显示全部楼层
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

查看全部评分

回复 支持 反对

使用道具 举报

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

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

之后你就基本明白了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 415044809 发表于 2014-10-19 02:12:54 | 显示全部楼层
搞出来啦,谢谢大家!
回复 支持 反对

使用道具 举报

xixihaha2014 发表于 2014-10-19 17:26:46 | 显示全部楼层
  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]
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 23:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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