LeetCode154 Find Minimum in Rotated Sorted Array II

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述


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];
}
};
分享到 评论