剑指 Offer 11. 旋转数组的最小数字

题目描述

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

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

注意，数组 $[a[0], a[1], a[2], …, a[n-1]]$ 旋转一次的结果为数组 $[a[n-1], a[0], a[1], a[2], …, a[n-2]]$ 。

示例 1：

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

示例 2：

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

提示：

$n == numbers.length$
$1 <= n <= 5000$
$-5000 <= numbers[i] <= 5000$
$numbers$ 原来是一个升序排序的数组，并进行了 $1$ 至 $n$ 次旋转

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

算法

(二分) $O(n)$

题目已知原来是一个非严格升序数组，有序性我们可以想到二分，经过旋转后原数组前一半有序后一半有序，但整体是无序的，但仍然可以用二分，二分只要满足两段性就可以使用，观察旋转后的数组前一半都是大于 $nums[0]$ 的后一半都是小于 $nums[0]$ 的，只要后面是小于 $nums[0]$ 的就可以二分答案。

算法步骤：

首先判断首尾是否相等，如果相等，则去掉尾部和 $nums[0]$ 相等的元素，为了可以二分答案。
如果当前数组已经有序，说明最小值就是 $nums[0]$。
否则二分答案，这里既可以二分最大值的位置，加 $1$ 就是答案，也可以直接二分最小值的位置。

时间复杂度

最坏情况下，如果数组中的值都是相等的，则需要遍历每个数，时间复杂度是 $O(n)$ 的，虽然二分的时间复杂度是 $logn$，但总时间复杂度为 $O(n)$。

空间复杂度

$O(1)$

C++ 代码

二分最小值位置

class Solution {
public:
    int minArray(vector<int>& nums) {
        int n = nums.size() - 1;
        while (n && nums[0] == nums[n]) n -- ;
        if (!n || nums[0] < nums[n]) return nums[0];
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};

二分最大值位置

class Solution {
public:
    int minArray(vector<int>& nums) {
        int n = nums.size() - 1;
        while (n && nums[0] == nums[n]) n -- ;
        if (!n || nums[0] < nums[n]) return nums[0];
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        return nums[r + 1];
    }
};