VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 153. 寻找旋转排序数组中的最小值

Posted on Edited on In , ,

摘要：
二分查找经典题，太tm经典了，对于理解二分查找真是好题。

题目

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

请找出其中最小的元素。

示例 1：

输入： nums = [3,4,5,1,2]
输出： 1

示例 2：

输入： nums = [4,5,6,7,0,1,2]
输出： 0

示例 3：

输入： nums = [1]
输出： 1

提示：

  • $1 <= nums.length <= 5000$
  • $-5000 <= nums[i] <= 5000$
  • nums 中的所有整数都是 唯一 的
  • nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转

二分查找

题目要求找到折叠后的递增数组的第二段递增序列的左端点。
可以利用二分的思想，如果 mid 落在左半边，那么左边界最低取到 mid+1；
如果 mid 落在右半边，那么右边界最高取到 mid。
问题是，如何判断 mid 落在哪一边。

因为折叠数组是从一个未知点折叠的，所以折叠数组左半边的所有数都大于等于第一个数，右半边都小于等于第一个数。依此可判断 mid 落在哪一边。

注意这一题有个很坑的地方，测试用例存在折叠数组完全递增的情况，也就是默认折叠点在数组下标范围之外。需要进行特判。

这一题的二分法找数字，利用目标值左半边和右半边的性质不同来缩小范围。
但是和该性质相关的点却是折叠数组的第一个数，而非目标值本身。
这一点尤为需要注意。一句话，想找目标值，在考虑性质的时候，不一定从目标值入手。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 执行用时: 8 ms
// 内存消耗: 9.7 MB
class Solution {
public:
    int len;
    int findMin(vector<int>& nums) {
        len = nums.size();
        int lo = 0, hi = len - 1;
        if (nums[hi] > nums[lo]) return nums[lo];       // 1
        int cmp = 0;                                    // 2
        for (; lo < hi;) {
            int mid = lo + hi >> 1;
            if (nums[mid] >= nums[cmp]) lo = mid + 1;
            else hi = mid;
        }
        return nums[lo];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 执行用时: 0 ms
// 内存消耗: 38 MB
class Solution {
    int len;
    public int findMin(int[] nums) {
        len = nums.length;
        int lo = 0, hi = len - 1;

        if (nums[hi] > nums[lo]) return nums[0];
 
        for (; lo < hi;) {
            int mid = lo + hi >> 1;
            if (nums[mid] >= nums[0]) lo = mid + 1;
            else hi = mid;
        }

        return nums[lo];
    }
}

原题链接： LeetCode 153. 寻找旋转排序数组中的最小值