微信公众号：路人zhang
网站救助计划

1.为阅读体验，本站无任何广告，也无任何盈利方法，站长一直在用爱发电，现濒临倒闭，希望有能力的同学能帮忙分担服务器成本


2.捐助10元及以上同学，可添加站长微信lurenzhang888，备注捐助，网站倒闭后可联系站长领取本站pdf内容


3.若网站能存活下来，后续将会持续更新内容

当前位置： 算法 > 剑指offer > 剑指 offer 11.旋转数组的最小数字

剑指 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：

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

示例 2：

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

提示：

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

算法

(二分) O(n)

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

算法步骤：

  1. 首先判断首尾是否相等，如果相等，则去掉尾部和 nums[0] 相等的元素，为了可以二分答案。
  2. 如果当前数组已经有序，说明最小值就是 nums[0]。
  3. 否则二分答案，这里既可以二分最大值的位置，加 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];
    }
};

Java 代码

二分最小值位置

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

二分最大值位置

class Solution {
    public int minArray(int[] nums) {
        int n = nums.length - 1;
        while (n > 0 && nums[0] == nums[n]) {
            n -- ;
        }
        if (n == 0 || 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];
    }
}

Python 代码

二分最小值位置

class Solution:
    def minArray(self, nums: List[int]) -> int:
        n = len(nums) - 1
        while n > 0 and nums[0] == nums[n]:
            n -= 1
        if n == 0 or nums[0] < nums[n]:
            return nums[0]
        l, r = 0, n
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] < nums[0]:
                r = mid
            else:
                l = mid + 1
        return nums[r]

二分最大值位置

class Solution:
    def minArray(self, nums: List[int]) -> int:
        n = len(nums) - 1
        while n > 0 and nums[0] == nums[n]:
            n -= 1
        if n == 0 or nums[0] < nums[n]:
            return nums[0]
        l, r = 0, n
        while l < r:
            mid = (l + r + 1) // 2
            if nums[mid] >= nums[0]:
                l = mid
            else:
                r = mid - 1
        return nums[r + 1]

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer