[LeetCode] 154. 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.
Thought process:
This would affect the time complexity. For example, the array could contain a bunch of 1s and one 0. If we do a binary search on it, we could have left = mid = right = 1. We don't know in which direction the 0 is. So in the worst case, the time complexity is O(n). But we can still use binary search to improve the average case run-time.
The idea is to eliminate the edge case where left = mid = right at the beginning of each loop. After that, if we compare nums[mid] with the last element in the array, there are two cases:
- nums[mid] <= last element: the minimum element is to the left of mid.
- nums[mid] > last element: the minimum element is to the right of mid.
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | public class Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; int last = nums[right]; while (left + 1 < right) { if (nums[left] == nums[right]) { left++; continue; } int mid = left + (right - left) / 2; if (nums[mid] <= last) { right = mid; } else { left = mid; } } if (nums[left] < nums[right]) { return nums[left]; } else { return nums[right]; } } } |
Time complexity:
O(logn) in the average case. O(n) in the worst case.
Comments
Post a Comment