题目描述
题目链接:154. Find Minimum in Rotated Sorted Array II
Suppose an array of length
n
sorted in ascending order is rotated between1
andn
times. For example, the arraynums = [0,1,4,4,5,6,7]
might become:
[4,5,6,7,0,1,4]
if it was rotated 4 times.[0,1,4,4,5,6,7]
if it was rotated 7 times.Notice that rotating an array
[a[0], a[1], a[2], ..., a[n-1]]
1 time results in the array[a[n-1], a[0], a[1], a[2], ..., a[n-2]]
.Given the sorted rotated array
nums
that may contain duplicates, return the minimum element of this array.
例子
例子 1
Input:
nums = [1,3,5]
Output:1
例子 2
Input:
nums = [2,2,2,0,1]
Output:0
Constraints
n == nums.length
1 <= n <= 5000
- `-5000 <= nums[i] <= 5000
nums
is sorted and rotated between1
andn
times.
Follow up
This is the same as
Find Minimum in Rotated Sorted Array
but with duplicates. Would allow duplicates affect the run-time complexity? How and why?
解题思路
这道题是在 [Leetcode]153. Find Minimum in Rotated Sorted Array(C++) 的基础上添加了元素有可能会重复的情况。基本思路是上一题差不多,但是当 Left == Right && Mid == Left
时,不能直接判断来确定 Mid
当前是在前半段还是后半段,这个时候我们只能通过右移左边界使得 Left != Right
才能继续判断,代码如下:
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
// move the left boundary if its equal to right boundary
while (left < right && nums[left] == nums[right]) {
left++;
}
// if the array is already sorted or there's only 1 element, break
if (left == right || nums[left] < nums[right]) {
break;
}
int mid = (left + right) / 2;
if (nums[mid] >= nums[left]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
};
- 时间复杂度:
O(log n) -> O(n)
- 空间复杂度:
O(1)
GitHub 代码同步地址: 154.FindMinimumInRotatedSortedArrayIi.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions