image.png
这个题是二分查找的典型题目，递归非递归都可以解决这个问题，首先我们用递归的额方式来看看，需要说明的是，递归本身用的栈一般不算在空间复杂度上。
递归求解：
class Solution {
public:
int findMin(vector<int>& nums) {
return findMinHelper(nums, 0, nums.size() - 1);
}
int findMinHelper(vector<int>& nums, int begin, int end) {
if (begin == end) return nums[begin];
if (end - begin == 1) return nums[end] > nums[begin] ? nums[begin] : nums[end];
if (nums[begin] < nums[end]) return nums[begin];
if (nums[begin] == nums[end]) {
int val = nums[begin];
while (begin < end) {
val = min(val, nums[begin]);
begin++;
}
return val;
}
int mid = (end - begin) / 2 + begin;
return min(findMinHelper(nums, 0, mid), findMinHelper(nums, mid + 1, end));
}
};
非递归求解，分三步，
- 如果 nums[m] 小于 nums[r] 说明最小值肯定不在右侧，肯定在左侧
- 如果 nums[m] 大于 nums[r] 说明最小值肯定不在左侧，在右侧
- 如果相等说明没有办法判断，那么只能一步一步来缩小范围，r--来操作
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size()-1;
while(l < r){
int m = l+((r-l)>>1);
if(nums[m] < nums[r]) r = m;
else if(nums[m] > nums[r]) l = m+1;
else r--;
}
return nums[l];
}
};
