Find Minimum in Rotated Sorted Array
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.
You may assume no duplicate exists in the array.
---------------------------------------------------------------
binary search
class Solution { public: int findMin(vector<int> &num) { if (num.size() == 1) return num[0]; if (num[0] < num.back()) return num[0]; int left = 0; int right = num.size() - 1; while (left <= right) { int mid = (left + right) / 2; if (num[mid] < num[mid - 1]) { return num[mid]; } if (num[mid] > num[right]) { left = mid + 1; }else { right = mid - 1; } } return -1; } };
Find Minimum in Rotated Sorted Array II
Follow up for "Find Minimum in Rotated Sorted Array":Suppose a sorted array is rotated at some pivot unknown to you beforehand.
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
(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.
--------------------------------------------------------
if num[mid] == num[right], then num[left] must equal to num[mid] as well
class Solution { public: int findMin(vector<int> &num) { if (num.size() == 1) return num[0]; if (num[0] < num.back()) return num[0]; int left = 0; int right = num.size() - 1; while (left <= right) { int mid = (left + right) / 2; if (num[mid] < num[mid - 1]) { return num[mid]; } if (num[mid] == num[right]) { right--; }else if (num[mid] > num[right]) { left = mid + 1; }else { right = mid - 1; } } return num[0]; } };
No comments:
Post a Comment