剑指offer11. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
输入：[3,4,5,1,2]
输出：1
思路
这道题简单的地方在于一眼能看出来是二分，难点在于特殊情况的考虑。
旋转操作让这个数组可以分成两个递增的数组，并且右边那个要更小。
最简单的情况，假设没有重复元素，左边数组的开头设为start, 那么我们始终有： e l e m e n t [ r i g h t ] < s t a r t element[right] < start element[right]<start
我们要找的拐点就是小于start的第一个数。这直接套二分查找就行。
特殊情况1：
搬了所有元素或没有搬任何元素，这样不存在两个子数组，这种情况，最右会大于最左(在没有重复元素时）。
特殊情况2：
存在相等元素：
- 相等元素在非切割点，这种气势不需要管，因为不影响我们最初的假设即 element[right] < start，譬如[3,4,5,5,1,2]
- 切割旋转点本身就在一系列相等元素中。譬如[1,2,2,2,4]–>[2,2,4,1,2]
- 这种情况下，不符合 e l e m e n t [ r i g h t ] < s t a r t element[right] < start element[right]<start，当一个元素=start的时候，无法判断它在左数组还是右数组
- 我对于这种情况的处理采取去重，也就是这个重复的元素k在最开始让它在左侧数组先消失。这对于找最小元素是没有影响的，反正右数组依然保留了这个k。 如果k是最小，可以在右数组找到；如果k不是最小，可以在有数组找到比k小的存在。如下所示，上下两个找旋转点是等价的。
[1,2,2,2,4] --> 旋转–> [2,2,4,1,2]
[1,2,4] --> 旋转 -->[4,1,2]
代码：
lass Solution {public: int minArray(vector<int>& numbers) { int left = 0; int right =numbers.size()-1; // 去除左边和最右重复的元素 while(left < right && numbers[left] == numbers[right]) left ; int start = numbers[left]; //最小值在旋转部分的开头，说明没有旋转 if(numbers[right]>numbers[left]) return start; while(left < right){ int mid = (left right)/2; int val = numbers[mid]; if(mid-1>=0 && val < numbers[mid-1]) // 确定找到拐点 return val; if(val>=start){ left = mid 1; } else if(val < start){ right = mid-1; } } return numbers[left]; }}; 赞 (0)