154. Find Minimum in Rotated Sorted Array II
Problem description:
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.
Example 1:
Input: [1,3,5]
Output: 1
Example 2:
Input: [2,2,2,0,1]
Output: 0
Solution:
This question is a follow up for 153. Find Minimum in Rotated Sorted Array. We can still use binary search to solve this question.
- two pointers,
left
andright
. In the end, we return thenums[left]
- calculate
mid
to find middle element. - Since the array is sorted, if
nums[mid] > nums[right]
then we setleft
tomid+1
because we know the smallest element is on the right side and it’s started position would at least be mid+1. - One thing to notice is that the array contains duplicate elements, if
nums[mid] == nums[right]
we reduce the right pointer.
For the duplicate elements, it might drag the time complexity to O(n)
if it looks like the following array."1 1 1 1 1 0 1 1 1 1 1 1 1 1"
1 | class Solution { |
reference: