|
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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];
}
};
来源：https://www./content-4-794451.html
|
