Problem:
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.
You may assume no duplicate exists in the array.
Idea:
Divide and conquer.
Evenly Split the array into two sub-arrays, and find the minimums of them, return the smaller one.
findMin(a[0..n]) = min(findMin(a[0..n/2], a[n/2..n])
Key property:
One of the sub-array will be a sorted array, it takes O(1) to find the minimal element, just the first element.
Time complexity:
T(n) = O(1) + T(n/2) = O(logn)
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int findMin(vector<int> &num) { return findMin(num, 0, num.size()-1); } private: int findMin(const vector<int>& num, int l, int r) { // Only 1 or 2 elements if (l+1 >= r) return min(num[l], num[r]); // Sorted if (num[l] < num[r]) return num[l]; int mid = l + (r-l)/2; return min(findMin(num, l, mid-1), findMin(num, mid, r)); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment