题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组[0,1,2,4,5,6,7]
可能变为[4,5,6,7,0,1,2]
)。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
样例
示例1:
输入: [1,3,5]
输出: 1
示例2:
输入: [2,2,2,0,1]
输出: 0
说明
-
这道题是 Find Minimum in Rotated Sorted Array 的延伸题目。
-
允许重复会影响算法的时间复杂度吗?会如何影响,为什么?
算法1
(预处理去重+二分) $O(n)$
思路与 Find Minimum in Rotated Sorted Array 相同。这里借用一下y总的图:
数组左半部的元素都满足大于等于nums.back()
,数组右半部的元素都满足小于等于nums.back()
,由于重复元素的存在,当nums[mid] == nums.back()
的时候并不能确定答案在哪半边,因为既有可能在左边也有可能在右边,所以先进行预处理将数组末尾与数组首项相同的元素去掉,这样数组左半部的元素就会严格大于nums.back()
,二分时我们的初始边界保证nums[l]
严格大于nums[r]
或者数组是未被旋转过的。
时间复杂度
最坏情况下假如数组元素全部相同,那么去掉末尾相同元素就会耗费$O(n)$的时间,因此总时间复杂度为$O(n)$。
C++ 代码
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
int t = r;
while (t > 0 && nums[t] == nums[0]) t -- ;
r = t;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] <= nums[t]) r = mid;
else l = mid + 1;
}
return nums[l];
}
};
算法2
(二分) $O(n)$
这道题也可以直接进行二分,不过更新边界与check(mid)
的逻辑与算法1不同。相对于与固定的数组末尾元素nums.back()
比较,因为有相同元素的存在,当nums[mid] == nums.back()
时我们无法确定最小值的位置,因此我们可以考虑每次与数组右边界元素nums[r]
比较。当中点nums[mid]
大于右边界元素nums[r]
时,nums[mid]
一定不是最小值,因为右边界已经比它严格小了,并且在mid
左边直到左边界的元素肯定也都不是最小值:首先数组一定是被旋转过的不然不会出现中间值大于右边界的值,那么因为旋转左边界的值就会大于等于右边界的值,所以左边界到mid
之间的值也会至少大于等于右边界的值,我们可以把左边界更新成mid + 1
。
同理我们考虑nums[mid]
小于右边界元素nums[r]
的情况,此时从[mid + 1, r]
之间的值都不会是最小值因为这一段是非严格单调递增的,但是nums[mid]
仍有可能是最小值,所以我们把右边界更新成mid
。
最麻烦的时候在nums[mid] == nums[r]
的时候,此时nums[mid]
有可能是最小值,如果不是那么最小值在mid
左边或右边都有可能,这时我们可以简单的缩小右边界,将右边界减一,即r = r - 1
。这样做的道理是首先最小值一定在[l, r]
之间,如果nums[r]
是最小值,那么[mid, r]
之间都是最小值,并且由于我们计算mid
时是左偏的即mid = l + r >> 1
所以中点mid
一定不会取到右边界上,这样我们将区间更新成[l, r - 1]
后可以保证答案仍在区间内,而且每一步区间都会严格的缩小,那我们一定会找到答案。
另外如果我们拿nums[mid]
与nums[l]
来比较则会出错,原因是nums[mid] > nums[l]
时最小值可能在mid
左边(比如数组未被旋转过),也有可能在mid
右边,不具有二分性。
时间复杂度
最坏情况下假如数组元素全部相同,时间复杂度依然是$O(n)$。
C++ 代码
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < nums[r]) r = mid;
else if (nums[mid] > nums[r]) l = mid + 1;
else r -- ;
}
return nums[l];
}
};