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.
The array may contain duplicates.
Idea:
Divide and conquer
Time complexity:
Average: O(logn)
Worst: O(n)
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { public: int findMin(vector<int> &num) { return findMin(num, 0, num.size()-1); } int findMin(const vector<int>& num, int l, int r) { // One or two elements, solve it directly if (l+1 >= r) return min(num[l], num[r]); // Sorted if (num[l] < num[r]) return num[l]; int m = l + (r-l)/2; // Recursively find the solution return min(findMin(num, l, m - 1), findMin(num, m, r)); } }; |
Related Problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment