剑指 Offer 11-旋转数组的最小数字(旋转数组的最小数字 LCOF)

原文链接: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

中文题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在重复元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。

示例 1：

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

示例 2：

输入：[2,2,2,0,1]
输出：0

注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

通过代码

高赞题解

解题思路：

为精简篇幅，本文将数组 $numbers$ 缩写为 $nums$ 。

如下图所示，寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 $nums[x]$ ，称 $x$ 为 旋转点 。

{:width=450}

排序数组的查找问题首先考虑使用 二分法 解决，其可将 遍历法 的 线性级别 时间复杂度降低至 对数级别 。

算法流程：

初始化： 声明 $i$, $j$ 双指针分别指向 $nums$ 数组左右两端；
循环二分： 设 $m = (i + j) / 2$ 为每次二分的中点（ “/“ 代表向下取整除法，因此恒有 $i \leq m < j$ ），可分为以下三种情况：
1. 当 $nums[m] > nums[j]$ 时： $m$ 一定在左排序数组中，即旋转点 $x$ 一定在 $[m + 1, j]$ 闭区间内，因此执行 $i = m + 1$；
2. 当 $nums[m] < nums[j]$ 时： $m$ 一定在右排序数组中，即旋转点 $x$ 一定在$[i, m]$ 闭区间内，因此执行 $j = m$；
3. 当 $nums[m] = nums[j]$ 时： 无法判断 $m$ 在哪个排序数组中，即无法判断旋转点 $x$ 在 $[i, m]$ 还是 $[m + 1, j]$ 区间中。解决方案： 执行 $j = j - 1$ 缩小判断范围，分析见下文。
返回值： 当 $i = j$ 时跳出二分循环，并返回 旋转点的值 $nums[i]$ 即可。

正确性证明：

当 $nums[m] = nums[j]$ 时，无法判定 $m$ 在左（右）排序数组，自然也无法通过二分法安全地缩小区间，因为其会导致旋转点 $x$ 不在区间 $[i, j]$ 内。举例如下：

设以下两个旋转点值为 $0$ 的示例数组，则当 $i = 0$, $j = 4$ 时 $m = 2$ ，两示例结果不同。
示例一 $[1, 0, 1, 1, 1]$ ：旋转点 $x = 1$ ，因此 $m = 2$ 在 右排序数组 中。
示例二 $[1, 1, 1, 0, 1]$ ：旋转点 $x = 3$ ，因此 $m = 2$ 在 左排序数组 中。

而证明 $j = j - 1$ 正确（缩小区间安全性），需分为两种情况：

当 $x < j$ 时： 易得执行 $j = j - 1$ 后，旋转点 $x$ 仍在区间 $[i, j]$ 内。
当 $x = j$ 时： 执行 $j = j - 1$ 后越过（丢失）了旋转点 $x$ ，但最终返回的元素值 $nums[i]$ 仍等于旋转点值 $nums[x]$ 。
1. 由于 $x = j$ ，因此 $nums[x] = nums[j] = nums[m] \leq number[i]$ ;
2. 又由于 $i \leq m <j$ 恒成立，因此有 $m < x$ ，即此时 $m$ 一定在左排序数组中，因此 $nums[m] \geq nums[i]$ ;

综合 1. , 2. ，可推出 $nums[i] = nums[m]$ ，且区间 $[i, m]$ 内所有元素值相等，即有：

$$
nums[i] = nums[i+1] = \cdots = nums[m] = nums[x]
$$

此时，执行 $j = j - 1$ 后虽然丢失了旋转点 $x$ ，但之后区间 $[i, j]$ 只包含左排序数组，二分下去返回的一定是本轮的 $nums[i]$ ，而其与 $nums[x]$ 相等。

综上所述，此方法可以保证返回值 $nums[i]$ 等于旋转点值 $nums[x]$ ，但在少数特例下 $i \ne x$ ；而本题目只要求返回 “旋转点的值” ，因此本方法正确。

补充思考： 为什么本题二分法不用 $nums[m]$ 和 $nums[i]$ 作比较？

二分目的是判断 $m$ 在哪个排序数组中，从而缩小区间。而在 $nums[m] > nums[i]$情况下，无法判断 $m$ 在哪个排序数组中。本质上是由于 $j$ 初始值肯定在右排序数组中； $i$ 初始值无法确定在哪个排序数组中。举例如下：

对于以下两示例，当 $i = 0, j = 4, m = 2$ 时，有 nums[m] > nums[i] ，而结果不同。
$[1, 2, 3, 4 ,5]$ 旋转点 $x = 0$ ： $m$ 在右排序数组（此示例只有右排序数组）；
$[3, 4, 5, 1 ,2]$ 旋转点 $x = 3$ ： $m$ 在左排序数组。

<,,,,,,,,>

复杂度分析：

时间复杂度 $O(\log_2 N)$ ： 在特例情况下（例如 $[1, 1, 1, 1]$），会退化到 $O(N)$。
空间复杂度 $O(1)$ ： $i$ , $j$ , $m$ 变量使用常数大小的额外空间。

代码：

[]
class Solution:
    def minArray(self, numbers: [int]) -> int:
        i, j = 0, len(numbers) - 1
        while i < j:
            m = (i + j) // 2
            if numbers[m] > numbers[j]: i = m + 1
            elif numbers[m] < numbers[j]: j = m
            else: j -= 1
        return numbers[i]

[]
class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
}

[]
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int i = 0, j = numbers.size() - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
};

实际上，当出现 $nums[m] = nums[j]$ 时，一定有区间 $[i, m]$ 内所有元素相等或区间 $[m, j]$ 内所有元素相等（或两者皆满足）。对于寻找此类数组的最小值问题，可直接放弃二分查找，而使用线性查找替代。

[]
class Solution:
    def minArray(self, numbers: [int]) -> int:
        i, j = 0, len(numbers) - 1
        while i < j:
            m = (i + j) // 2
            if numbers[m] > numbers[j]: i = m + 1
            elif numbers[m] < numbers[j]: j = m
            else: return min(numbers[i:j])
        return numbers[i]

[]
class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else {
                int x = i;
                for(int k = i + 1; k < j; k++) {
                    if(numbers[k] < numbers[x]) x = k;
                }
                return numbers[x];
            }
        }
        return numbers[i];
    }
}

[]
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int i = 0, j = numbers.size() - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else {
                int x = i;
                for(int k = i + 1; k < j; k++) {
                    if(numbers[k] < numbers[x]) x = k;
                }
                return numbers[x];
            }
        }
        return numbers[i];
    }
};

统计信息

通过次数	提交次数	AC比率
282953	574778	49.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途