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.
153. Find Minimum in Rotated Sorted Array 的拓展,这个题里允许有重复的元素。原来是依靠中间和边缘元素的大小关系,来判断哪一半是有序的。而现在因为重复元素的出现,如果遇到中间和边缘相等的情况,就无法判断哪边有序,因为哪边都有可能有序。假设原数组是{1,2,3,3,3,3,3},那么旋转之后有可能是{3,3,3,3,3,1,2},或者{3,1,2,3,3,3,3},判断左边缘和中心的时候都是3,就不知道应该截掉哪一半。解决的办法是对边缘移动一步,直到边缘和中间不在相等或者相遇,这就导致了会有不能切去一半的可能。所以最坏情况就会出现每次移动一步,总共移动n,算法的时间复杂度j: O(logn) ~ O(n)。
Java:
public int findMin(int[] num) { if(num == null || num.length==0) return 0; int l = 0; int r = num.length-1; int min = num[0]; while(l<r-1) { int m = (l+r)/2; if(num[l]<num[m]) { min = Math.min(num[l],min); l = m+1; } else if(num[l]>num[m]) { min = Math.min(num[m],min); r = m-1; } else { l++; } } min = Math.min(num[r],min); min = Math.min(num[l],min); return min; }
Python:
class Solution(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ left, right = 0, len(nums) - 1 while left < right: mid = left + (right - left) / 2 if nums[mid] == nums[right]: right -= 1 elif nums[mid] < nums[right]: right = mid else: left = mid + 1 return nums[left]
Python:
class Solution2(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ left, right = 0, len(nums) - 1 while left < right and nums[left] >= nums[right]: mid = left + (right - left) / 2 if nums[mid] == nums[left]: left += 1 elif nums[mid] < nums[left]: right = mid else: left = mid + 1 return nums[left]
C++:
class Solution { public: int findMin(vector<int> &nums) { if (nums.empty()) return 0; int left = 0, right = nums.size() - 1, res = nums[0]; while (left < right - 1) { int mid = left + (right - left) / 2; if (nums[left] < nums[mid]) { res = min(res, nums[left]); left = mid + 1; } else if (nums[left] > nums[mid]) { res = min(res, nums[right]); right = mid; } else ++left; } res = min(res, nums[left]); res = min(res, nums[right]); return res; } };
类似题目:
[LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索
[LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索 II
[LeetCode] 153. Find Minimum in Rotated Sorted Array 寻找旋转有序数组的最小值
All LeetCode Questions List 题目汇总