旋转数组的最小数字

xiaoxiao2021-03-01  11

题目描述

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

本题给的也算是有序数列,一看就应该和二分沾边,事实也是这样。

题目给的是非递减序列,就是说有可能会有重复的数字,要注意一下。

来简单分析一下数组的可能。

旋转过、没旋转过、所有元素都相等。

看题目吧旋转过的数组分成两半,{3,4,5,} {1,2}。

可以看出如果旋转过前面的数组所有元素一定大于后面的所有元素。

如果没旋转过的话,首元素一定比尾元素要小。

如果中间元素大于尾元素,最小值一定在后半段。

如果中间元素小于首元素,最小值一定在前半段。

查到最后一定是剩两个元素,后面的就是最小值,如果前面的是最小值就是没旋转的情况。

class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { if(rotateArray.size() == 0) return 0; int left=0; int right=rotateArray.size()-1; if(rotateArray[left] < rotateArray[right]) return rotateArray[left]; int mid; while(left<right) { mid =(left+right)/2; if(right-left==1) { mid=right; break; } if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid]) { int result=rotateArray[left]; for(int i=left+1;i<=right;i++) { if(rotateArray[i]<result) { return rotateArray[i]; } } } else if(rotateArray[left]>rotateArray[mid]) right=mid; else //if(rotateArray[right]<rotateArray[mid]) left=mid; } return rotateArray[mid]; } };

 

转载请注明原文地址: https://www.6miu.com/read-3850222.html

最新回复(0)