153-154. Find Minimum in Rotated Sorted Array

153 Find Minimum in Rotated Sorted Array

"Suppose an array sorted in ascending order 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."

这是一个增序列但是是rotate了的，我们要找最小值。
除了右下图没有rotate的特例，最小值一定发生在那个Jump 处。

Untitled drawing.jpg

如果二分的话，从中间劈开，其中一边肯定是递增的，另外一边有可能是递增的，也有可以是有那个jump.
我们要找的是有那个jump的那一半.
所以我们先看右边那一半是不是递增的，如果是递增的，那我扔掉右边那一半。
如果不是递增的，那我扔掉左边那一半。
每次可以扔掉一半，所以可以用二分。

有两处细节我在下面代码里标注了

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] < nums[r]) r = m; // m有可能是最小值，所以不能取m-1;
           // 为什么这里不用nums[l] 和nums[m]比较？文章末尾有讨论。
            else l = m + 1; // m不可能是最小值，所以可以取m + 1;
        }
        return nums[l];
    }
};

退出循环的条件：当只剩下一个数的时候。

再来考虑一下会不会stuck在只有两个数的case上呢？
当只有两个数时，m = l + (r - l) / 2, m取值l, 下一步要么 r 移过来(r = m)，要么l = m + 1移过去。
下一步只有一个数，所以不会死锁在两个数的case上。

代码里我们比较了右边的一段（看右边这一段是不是递增的），能不能比较左边的那一段？
其实也是可以的，但m的取值要改成 m = r - (r - l) / 2;
这是因为在只有两个数的时候这样的取法保证了你比较的那一段有两个数。否则只有一个数没有意义。

154 Find Minimum in Rotated Sorted Array II

这一题就是数字有重复的情况，
当nums[m] 和nums[r]相等的时候，我们无法做任何判断，我们只能说如果丢掉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) / 2;
            if (nums[m] == nums[r]) r--; //无法更进一步优化，只能说丢掉r也不会丢掉解。
            else if (nums[m] < nums[r]) r = m;
            else l = m + 1;
        }
        return nums[l];
    }
};

最后编辑于：2019.12.30 06:01:43