《剑指offer》旋转数组的最小数字

题目链接：?rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减序列的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

思路

直接线性扫描肯定是最简单的想法，但是我们要寻找更好的解法，那么我们就需要使用二分的思想。

我们知道对于旋转数组而言，左右肯定是排好序的，那么我们二分的时候可以每次比较最左端最右端与中间位置的数字，，然后再决定左右指针的移动方向。

但是我们还要考虑全面，如果当左指针，右指针与中间指针指向的数值相等我们该怎么处理呢？这个时候我们不能确定到底该移动哪个指针，那么此时我们就应该线性来扫描这个区间了。

class Solution{public:int _min(vector<int> a,int l,int r){int minx = a[l];for(int i = l+1; i<=r; i++)minx = min(minx,a[i]);return minx;}int minNumberInRotateArray(vector<int> a){int len = a.size();if(len==0)return 0;int l = 0,r = len-1;int mid = l;while(a[l]>=a[r]){if(r-l==1){mid = r;break;}mid = (l+r)/2;if(a[mid]==a[l] && a[mid]==a[r]){return _min(a,l,r);}if(a[mid]>=a[l])l = mid;else if(a[mid]<=a[r])r = mid;}return a[mid];}};

懂得接受失败的人，就是懂得人生真谛的人，

相关文章：

你感兴趣的文章：

标签云：