此类问题,不管是求最大值还是最小值,都是二分问题中的经典问题。对于这类问题晚上也都有很多经典的解析,但大多数都忽略了一个最重要的问题:到底是选取nums[0]
还是nums.back()
作为参考点,以及为什么?
我翻阅了一些解析,就拿上面所列出的这道题,很多答案直接就说:拿nums.back()
做参考点,只要nums[mid]>nums.back()
,那么最小值就肯定在nums[mid]
的右边(开区间);反之,只要nums[mid]<nums.back()
,那么最小值肯定在nums[mid]
的左边(闭区间);
那么问题来了,我拿nums[0]
做参考点不是照样满足条件吗?然后用nums[0]
去做题,ok,马上就错了,举个case:[2,0,2,2,2,2,2]
,最后就得不到正确答案;
原因出在哪里?其实不难想,就是当nums
数组本身就没有旋转的时候,此时nums[left]
就已经是最小值了,但是由于先前是拿nums[left]
做参考点,所以反而会跳过这个最小值;
拿nums.back()
做参考点就一定不会出现这个问题吗?其实不然,只要题目换成了去找最大值,照样要出问题。所以很多题解都是写的半懂不懂,很多道理都没有说清楚。
总结一下,其实找哪个参考点,是左边还是右边,都无所谓,关键是针对特殊case去做一些特殊处理。
下面是找出这个问题之后,以nums[0]
为参考点的答案:
class Solution {
public:
int findMin(vector<int>& nums) {
int len = nums.size();
int left = 0, right = len-1;
int ans = INT_MAX;
while(left < right){
int mid = left + (right-left) / 2;
if(nums[mid] == nums[left]){
ans = min(ans, nums[left++]);
continue;
}
if(nums[mid] > nums[left]){
ans = min(ans, nums[left]); // 重点就在这里
left = mid + 1;
} else {
right = mid;
}
}
return min(ans, nums[left]);
}
};
网友评论