LeetCode154 Find Minimum in Rotated Sorted Array II


描述


Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

样例

1
2
3
4
Input:
[3, 3, 3, 1, 2, 3]
Output:
1

思路

LeetCode153 Find Minimum in Rotated Sorted Array的加强版,现在多了元素会重复这个条件。

由于原始数组单调,不妨考虑二分,但是怎么更新$l$和$r$呢?

如果此时位于$mid$的元素大于位于$r$的元素,那么说明$mid$正位于中枢元素的左侧(中枢元素就是0),即$[l, mid]$这一段区间都不可能是答案,于是更新l = mid + 1

反之,说明$mid$位于中枢元素的右侧(或者就是中枢元素本身),于是更新r = mid

两道题的思路其实差不多,但是现在得考虑元素重复带来的影响。

也就是说如果出现$mid$的元素和$r$的元素相等的情况该怎么办?更新$l$还是更新$r$,以及怎么更新?

比如对于样例

1
2
3
[3, 3, 3, 1, 2, 3]
↑ ↑ ↑
l=0 mid=2 r=5

可能会认为此时应该l = mid + 1

再考虑如下样例

1
2
3
[3, 1, 2, 3, 3, 3, 3]
↑ ↑ ↑
l=0 mid=3 r=6

此时又应该是r = mid

出现这种情况的原因是,我们没办法判断中枢元素到底位于mid的左侧还是右侧,也就没办法进行相应的更新。

因此,遇到$mid$元素和$r$元素相等的情况,需要考虑打破这种相等状态,一种可能的方式是:只是将 $r$减一。

万一nums[r]是答案,将$r$减一会不会让最小值丢失?

不会的,因为nums[r] == nums[mid],中间的nums[mid]还在呢。

那为什么不是将$l$加一,不是也有可能改变相等的情况吗?

因为现在的写法是$mid$和$r$比较。在这种写法下,如果通过$l$加1来打破相等状态,有可能会越过中枢元素。

比如考虑如下样例

1
2
3
4
5
第一次二分:
[3, 1, 2, 3, 3, 3, 3]
↑ ↑ ↑
l=0 mid=3 r=6
mid元素和r元素相等,l++
1
2
3
4
5
6
第二次二分:
[3, 1, 2, 3, 3, 3, 3]
↑ ↑ ↑
l=1 mid=3 r=6
mid元素还是和r元素相等,l++
此时l=2,已经越过了中枢元素

因此如果想用$l$加1,那么在二分的时候就得用$mid$和$l$做比较。

但是还是不推荐用$l$来和$mid$作比较,考虑如下样例

1
2
3
[1, 3]
l = 0, r = 1, mid = 0
l和mid相等,l++,又错过了中枢元素...

因此遇到相等的情况,仅仅让$r$减一是比较保险的做法。


接下来说说复杂度的事情。

虽然打着“二分”的旗号,可能认为复杂度是$\mathcal{O}(logn)$。

在没有重复元素的时候,复杂度确实是这样,但是有重复元素的时候,却要小心了。

考虑样例 [1, 1, 1, 1, 1, 1]

那么每次都会碰到相等的情况,只能简单的r--,相当于遍历一遍数组,复杂度又退化到$\mathcal{O}(n)$了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
int cnt = 0;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] > nums[r]) l = m + 1;
else if (nums[m] < nums[r]) r = m;
else r--;
}
return nums[l];
}
};