旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减序列的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
题目链接：?rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
这样的解法并不能得到面试官的认可，也没有体现这道题原有的价值，我们应该寻找更加快捷的解法，二分，让中间结点来确定下一次缩小的范围（eg：3 4 5 1 2，下一次就是5 1 2，，下一次就是5 1；当right-left==1的时候退出，时间复杂度是O(log n)，但是有些例子并不满足，eg 1 0 1 1 1 和1 1 1 0 1）是的这里还需要特判这样的情况当两边的值和中间的值都相等的时候，我们应该把right的值向前移，类似于暴力，每错，就是枚举（eg：1 1 1 1 1）那么你只能枚举了。
做面试题，不仅仅要把题ac了，还要思考时间和空间复杂度，以及更优解，必须学会边界值的判断防止不必要的错误。
#include<stdio.h>#include<iostream>#include<vector>using namespace std;class Solution{public://暴力。int minNumberInRotateArray1(vector<int> rotateArray){int mmin=0x7FFFFFFF;for(int i=0; i<rotateArray.size(); i++)mmin=min(rotateArray[i],mmin);return mmin==0x7FFFFFFF?0:mmin;//空数组返回0}//单调性int minNumberInRotateArray2(vector<int> rotateArray){if(rotateArray.size()==0) return 0;int mmin=rotateArray[0];for(int i=1; i<rotateArray.size(); i++){if(rotateArray[i]>=mmin)continue;if(rotateArray[i]<mmin) {mmin=rotateArray[i];break;}}return mmin;}//二分int minNumberInRotateArray3(vector<int> rotateArray){if(rotateArray.size()==0) return 0;int mmin=0x7FFFFFFF;int left=0;int right=rotateArray.size()-1;if(left==right||rotateArray[left]<rotateArray[right]) return rotateArray[left];int mm;while(left<right){mm=(left+right)/2;if(rotateArray[left]==rotateArray[right]&&rotateArray[right]==rotateArray[mm]){right–;}else if(rotateArray[left]<=rotateArray[mm]&&rotateArray[right]<rotateArray[mm]){left=mm;}else if(rotateArray[left]>rotateArray[mm]&&rotateArray[right]>=rotateArray[mm]){right=mm;}if(right-left==1) {mmin=min(rotateArray[left],rotateArray[right]);break;}}return mmin==0x7FFFFFFF?0:mmin;//空数组返回0}};int main(){Solution so;vector<int> arr;int n,a;scanf("%d",&n);while(n–){cin>>a;arr.push_back(a);}int ans1=so.minNumberInRotateArray1(arr);printf("%d\n",ans1);int ans2=so.minNumberInRotateArray2(arr);printf("%d\n",ans2);int ans3=so.minNumberInRotateArray3(arr);printf("%d\n",ans3);return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
人生就是要感受美丽的善良的，丑恶的病态的。
