二分法——重复情形

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。注意数组中可能存在重复的元素。(Cf. LeetCode,2020)

这道题目被标记为困难。与题目基本一致但是被标记为中等的题目的区别在于数组中存在的重复元素。

这种题目类似于找零点，早在400年前，牛顿就已经给出了二分法的解决方案。而现在，我们的基本思路也是二分法，这可以让程序运行控制在 $O(lgN)$ 的时间复杂度里。但是这种方法存在一定的缺陷。在数学上，这样的二分法是失效的。比如这样一个数组：

[3,3,1,3]

我们可以看到左边界、右边界和中点（不论是哪种取整意义上的，我们还可以加一个[3,1,3,3]，没有任何的区别。）都是3.这样的数组，最小元素同时可能存在于左区间、右区间或者端点值里。这个时候，需要使用一些方法来在不变换的同时缩小区间。我们可以想到这个部分开始作枚举。

下面的代码使用了这一观点，但是通过巧妙的判断，将枚举的时间最小化。

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty())return 0;
        return findMin(nums.begin(), nums.end() - 1);
    }
    int findMin(vector<int>::iterator begin, vector<int>::iterator end) {
        // *begin>=*end,or not rotated.
        if (*begin < *end)
            return *begin;
        if(begin==end)return *begin;
        if(end-begin==1)return *end;
        auto mid = begin + (end - begin) / 2;
        if (*mid<*end)return findMin(begin,mid);
        else if(*mid>*end)return findMin(mid,end);
        else return findMin(begin,end-1);
    }
};

每次枚举后再进行判断，这样使得能够二分的时候都在二分，平均复杂度就更接近 $Θ(lgN)$ 一些。

Ads by Google

Read our privacy policy on how these personalized advertisements are delivered to you.

For your reading experience, we provide full-text RSS feeds. Although math formulas cannot be displayed well, the interface can be adjusted as you like and there are no ads.