本文共 1448 字，大约阅读时间需要 4 分钟。
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。示例 1：
输入：[3,4,5,1,2]
输出：1 示例 2：输入：[2,2,2,0,1]
输出：0C++
class Solution { //二分查找，时间复杂度O(logn)，空间O(1) /* index1只指向前边增数组； index2只指向后边增数组； 停止条件 index2-index1==1,index2所指即为所求 特殊： 1.旋转数组只旋转了0个元素，index1的值小于等于index2的值，index1所指即为所求； 2.一般情况，index1所指值>index2所指，index1所指==index2所指==mid所指，这种情况需要顺序查找，因为无法确定是哪一个index移动 */public: int minArray(vector & numbers) { int n=numbers.size(); int index1=0; //前边递增数组 int index2=n-1; //特殊情况1 if(numbers[index1] =numbers[index2]){ //判断是否满足停止条件 if(index2-index1==1) { mid=index2; break; } mid=index1+(index2-index1)/2; //特殊情况2 if(numbers[index1]==numbers[index2]&&numbers[index1]==numbers[mid]){ return minInorder(numbers,index1,index2); } if(numbers[index1]<=numbers[mid]){ index1=mid; }else if(numbers[index2]>=numbers[mid]){ index2=mid; } } return numbers[mid]; } int minInorder(vector & numbers,int index1,int index2){ int res=numbers[index1]; for(int i=index1;i<=index2;i++){ res=min(res,numbers[i]); } return res; }}; 转载地址：http://jvfdi.baihongyu.com/