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.
思路
可以利用传统的二分搜索法来解决这个问题。我们很容易知道,如果第一个数比最后一个数要大,说明它经过了某种方法的旋转。所以说,我们可以找到最大元素紧接着的那个元素,就是最小的元素了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
class Solution { public: int (vector<int>& nums) { int len = nums.size(); if (nums[0] <= nums[len-1]){ return nums[0]; } else{ int low = 0; int high = len-1; int mid = (low + high) / 2; while(low < high){ if(nums[mid] > nums[high]){ low = mid + 1; } else{ high = mid; } mid = (low + high) / 2; } return nums[mid]; } } };
|
近期评论