一: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.
数组中没有重复元素。
代码:
class Solution {
public:
int findMin(vector<int>& nums) { int low = ;
int high = nums.size()-; while(low<=high){ int mid = low + (high-low)/;
if(nums[mid] == nums[high]){
high--;
}else if(nums[mid] > nums[high]){
low = mid+;
}else{
high = mid;
}
} return nums[low];
}
};
二:Find Minimum in Rotated Sorted ArrayII
与一不同的是,其允许有重复元素
class Solution {
public:
int findMin(vector<int>& nums) { int low = ;
int high = nums.size()-; while(low<=high){ int mid = low + (high-low)/;
if(nums[mid] == nums[high]){
high--;
}else if(nums[mid] > nums[high]){
low = mid+;
}else{
high = mid;
}
} return nums[low];
}
};