LeetCode153-寻找旋转排序数组中的最小值

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

中文链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

题目详述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

1
2
输入: [3,4,5,1,2]
输出: 1

示例 2:

1
2
输入: [4,5,6,7,0,1,2]
输出: 0

题目详解

”数组 + 有序“可以联想到二分查找。升序排序的数组如果没有旋转，最小的元素就是第一个元素。升序排序的数组如果旋转了，拐点处的两个元素（最大的元素和最小的元素）是降序的，其他地方是局部升序的。利用二分查找找到这两个点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class LeetCode_00153 {

    public int findMin(int[] nums) {
        if (nums.length == 1) {     // 只有一个元素直接返回
            return nums[0];
        }
        int lo = 0;
        int hi = nums.length - 1;
        if (nums[0] < nums[hi]) {   // 没有旋转，整个序列是升序的
            return nums[0];
        }
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[mid + 1]) {    // nums[mid] 是最大值
                return nums[mid + 1];
            }
            if (nums[mid - 1] > nums[mid]) {    // nums[mid-1] 是最大值
                return nums[mid];
            }
            if (nums[mid] > nums[lo]) {         // lo 和 mid 在同一边
                lo = mid + 1;
            } else {                            // lo 和 mid 不在同一边
                hi = mid - 1;
            }
        }
        return -1;
    }
}

也可以运用二分查找缩小区间的方式来找到这个最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LeetCode_00153 {

    public int findMin(int[] nums) {
        // 可能的上下限
        int l = 0, r = nums.length - 1;
        // 缩小区间直至只有一个元素
        while (l < r) {
            int mid = l + r >>> 1;
            if (nums[mid] <= nums[r]) r = mid;  // 说明 mid 之后的元素都不可能是最小值
            else l = mid + 1;                   // 说明 mid 及之前的元素都不可能是最小值
        }
        return nums[r];
    }
}