154 Find Minimum in Rotated Sorted Array II
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 a sorted array 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多了一点点
public int findMin(int[] nums) {
if(nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] > nums[right]) {
left = mid + 1;
} else if(nums[mid] < nums[right]) {
right = mid;
} else {
right--;
}
}
return nums[left];
}
第13行,当nums[mid] == nums[high]的时候high--