美文网首页
关于旋转数组的最值寻找问题

关于旋转数组的最值寻找问题

作者: 老杜振熙 | 来源:发表于2021-04-09 22:15 被阅读0次

寻找旋转数组中的极小值 - leetcode

此类问题,不管是求最大值还是最小值,都是二分问题中的经典问题。对于这类问题晚上也都有很多经典的解析,但大多数都忽略了一个最重要的问题:到底是选取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]);
    }
};

相关文章

网友评论

      本文标题:关于旋转数组的最值寻找问题

      本文链接:https://www.haomeiwen.com/subject/fdnwkltx.html