首页 > 代码库 > leetcode -Find Minimum in Rotated Sorted Array II (1)
leetcode -Find Minimum in Rotated Sorted Array II (1)
本人大三狗，大一学物理，大二转专业来了计院。一入计院深似海，从此节操是路人。转眼间一年过去了，基本上课本的知识学的很好，考前突击分数还很光鲜，但是总是觉得空虚。因为在这个讲究技术的年代，没有一点技术压身，是很容易睡不着觉的。近日阅读了不少前人的经验教训，感觉自己的目标很明确，应届入bat，有必要考个研也没问题，保研估计没戏了。在这个讲究实战的年代，我有必要积累一点代码行数了，否则坑定是混不过面试的。而且还自以为是地定制了一批书单，现在看到堆到50cm搞的一堆书，也觉得压力山大。我就是属于这种书看的少，做的少，但是想的多的人。今后一定要改掉这个习惯！不说了，先从leetcode入手。将来来还有uva oj，geeksforgeeks。路漫漫其修远兮，吾将上下而求索。路是要一步一步走的，来了计院有一年了，也大概知道要怎么走了。今开此博客，记录自己的学习经历，希望它能够见证我的成长！也希望自己不虚此言，脚踏实地。
Find Minimum in Rotated Sorted Array II
Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.
关键词：array binary
这个问题要简单起来很容易，遍历一次数组，找出最小的数，只是时间复杂度只能做到O(n)。
int min(int a,int b){ if(a<b) return a; else return b;}//a,b谁更小class Solution{public: int findMin(vector<int>&num){ if(num.size()==0) return 0; if(num.size()==1) return num[0]; if(num.size()==2) return min(num[0],num[1]); int l=0; int r=num.size()-1; if(num[l]>num[r]){//如果左边的数比右边的大 while((l+1)!=r){ int mid=l+r;//暴力法 mid/=2; if(num[l]<=num[mid])//比中值大，把左边的舍去 l=mid; else r=mid;//比中指小，把右边的舍去 } return min(num[l],num[r]); }//单独考虑很多数字都相同，而其中一小部分不同的数中恰恰又最小的数的情况 else if(num[l]==num[r]){ int m; for(int i=1;i<(num.size()-1);i++) if(num[i]<m) m=num[i]; return m; } else //如果最左边的数小于最右边的数，直接返回最左边的数 return num[l]; }};
leetcode -Find Minimum in Rotated Sorted Array II (1)