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.
Have you met this question in a real interview?
Yes
Example
Given
[4, 5, 6, 7, 0, 1, 2]
return 0
Note
Tags Expand
You may assume no duplicate exists in the array.
Initial solution:
Time: O(n)
Space: O(1)
Compare adjacent elements one by one until find an element is less than the element before it.
class Solution { public: /** * @param num: a rotated sorted array * @return: the minimum number in the array */ int findMin(vector<int> &num) { // write your code here int len = num.size(); if(len == 0) return 0; int pivot = 0; for(int i = 1; i < len; i++){ if(num[i] < num[i - 1]) pivot = i; } return num[pivot]; } };
Binary search:
Set the num[0] as target to search, then start will point to the first element < num[0].
Note: when the sorted array is not rotated, no element < num[0], start will equal to the size of array.
We need to differentiate this situation.
Time: O(logn)
Space: O(1)
class Solution { public: /** * @param num: a rotated sorted array * @return: the minimum number in the array */ int findMin(vector<int> &num) { // write your code here int start = 0; if(num.size() == 0) return 0; int end = num.size() - 1; while(start <= end){ int mid = (start + end) / 2; if(num[mid] < num[0]) end = mid - 1; if(num[mid] >= num[0]) start = mid + 1; } if(start == num.size()) return num[0]; return num[start]; } };
Lintcode second:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution { public: /** * @param num: a rotated sorted array * @return: the minimum number in the array */ //8:25 -- 8:42 int findMin(vector<int> &num) { // write your code here if(num.size() == 0) return 0; int start = 0; int end = num.size() - 1; while(start <= end){ int mid = (start + end) / 2; //start 从左往右第一个<= num[0] //end 从右往左 第一个>num[0] if(num[mid] >= num[0]) start = mid + 1; else end = mid - 1; } if(start == num.size()) return num[0]; return num[start]; } }; |
没有评论:
发表评论