题目描述（困难难度）
153 题 升级版，依旧是旋转过的数组，一个排序好的数组，把前边的若干的个数，一起移动到末尾，找出最小的数字。只不过这道题中的数字可能有重复的。
思路分析
想一下 153 题 我们怎么做的。
mid 和 end 比较。
mid < end：最小值在左半部分。
mid > end：最小值在右半部分。
所以我们只需要把 mid 和 end 比较，mid < end 丢弃右半部分（更新 end = mid），mid > end 丢弃左半部分（更新 start = mid + 1）。直到 end 等于 start 时候结束就可以了。
之前没有重复的数字，所以 mid 要么大于 end ，要么小于 end。这里的话，就需要考虑如果 mid == end 的话，我们该怎么做。代码框架也就出来了。
public int findMin(int[] nums) {
int start = 0;
int end = nums.length - 1;
while (start < end) {
int mid = (start + end) >>> 1;
if (nums[mid] > nums[end]) {
start = mid + 1;
} else if (nums[mid] < nums[end]) {
end = mid;
} else {
//添加代码
}
}
return nums[start];
}
可以想几个例子考虑下。
3 3 1 2 3 3 3 3 3
^ ^
mid end
上边的情况， mid == end，此时最小值在 mid 左边
3 3 3 3 3 2 3
^ ^
mid end
上边的情况， mid == end，此时最小值在 mid 右边
2 3 3 1 1 1 1 1 1
^ ^
mid end
上边的情况， mid == end，此时最小值在 mid 左边
当相等的时候，最小值可能在左边，也可能在右边，问题的关键就是去解决这个问题。
想法一
我想到的一种解决方案是如果遇到了相等的情况，将 mid 指针不停的向左滑动，直到当前的值不再等于 end。然后就会有三种情况。
情况一，移动结束的值小于了
end，此时最小值一定在mid的左边3 3 1 2 3 3 3 3 3 ^ ^ mid end情况二，移动结束的值大于了
end，此时最小值一定是结束位置的后一个值2 3 3 1 1 1 1 1 1 ^ ^ mid end情况三，移动到头后依旧是等于
end，此时最小值一定在mid的右边3 3 3 3 3 2 3 ^ ^ mid end
大于小于等于也只有上边的三种情况了，所以代码也就出来了。
public int findMin(int[] nums) {
int start = 0;
int end = nums.length - 1;
while (start < end) {
int mid = (start + end) >>> 1;
if (nums[mid] > nums[end]) {
start = mid + 1;
} else if (nums[mid] < nums[end]) {
end = mid;
} else {
int temp = mid;
//不停前移
while (temp >= 0) {
if (nums[temp] == nums[end]) {
temp--;
//情况一
} else if (nums[temp] < nums[end]) {
end = mid;
break;
//情况二
} else {
return nums[temp + 1];
}
}
//情况三
if (temp == -1) {
start = mid + 1;
}
}
}
return nums[start];
}
想法二
参考 这里 ，非常简洁优雅。
主要思想就是把问题转换回 153 题 ，同样也是解决相等的时候怎么办。
只做一件事，end--。因为 mid 和 end 相等，所以我们直接把 end 抛弃一定不会影响结果的。
public int findMin(int[] nums) {
int start = 0;
int end = nums.length - 1;
while (start < end) {
int mid = (start + end) >>> 1;
if (nums[mid] > nums[end]) {
start = mid + 1;
} else if (nums[mid] < nums[end]) {
end = mid;
} else {
end--;
}
}
return nums[start];
}
想法三
参考 这里 。
首先根据题目的意思，数组是被分成了两段。
当有重复数字的时候，之所以麻烦，就是因为有一个重复数字可能会被切割在两段里，比如下边的例子。
3 3 1 2 3 3 3 3 3
^ ^
mid end
分成了 3 3 和 1 2 3 3 3 3 两段，3 同时处于两段
3 3 3 3 3 2 3
^ ^
mid end
分成了 3 3 3 3 和 2 3 两段，3 同时处于两段
而如果所有重复的数字只处于一段里，其实并不复杂，比如下边的例子
1 2 3 3 3 3
^ ^
mid end
只有一段 1 2 3 3 3 3
7 7 6 6 6
^ ^
mid end
分成了 7 7 和 6 6 6 两段，没有数字处于两段里
对于上边的情况，其实我们可以确定，当 mid 和 end 相等的时候，最小值一定在 start 到 mid 之间。也就是和 mid < end 的情况一致的。
所以我们可以做一个预处理，保证所有重复数字不在两段里出现即可，再简单化，也就是保证切割的位置不要是重复数字。也就是比较 start 和 end 是否相同，相同的话 end-- 即可。
while (nums[end] == nums[start] && end > start) {
end--;
}
最后只要把 153 题 的代码拿过来即可。
public int findMin(int[] nums) {
int start = 0;
int end = nums.length - 1;
while (nums[end] == nums[start] && end > start) {
end--;
}
while (start < end) {
int mid = (start + end) >>> 1;
if (nums[mid] > nums[end]) {
start = mid + 1;
} else{
end = mid;
}
}
return nums[start];
}
总
思路一主要是对新出现的情况进行细分来解决问题，思路二和思路三是把问题向原先的问题靠拢，从而尽可能少的变动了代码。不过这道题由于一些情况很特殊，所以虽然用了二分，最坏时间复杂度也降到了 O(n)，不再是 log 级的。