leetcode-旋转数组的最小数字

78 阅读 0 评论 52 点赞

我是靠谱客的博主曾经百褶裙，最近开发中收集的这篇文章主要介绍leetcode-旋转数组的最小数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目来自LeetCode，链接：面试题11. 旋转数组的最小数字。具体描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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

首先最简单的当然是顺序搜索，遍历数组，找到第一个比其前面数小的就是要找的结果。时间复杂度为 $O (n)$ ，空间复杂度为 $O (1)$ 。

JAVA版代码如下：

class Solution {
    public int minArray(int[] numbers) {
        for (int i = 1; i < numbers.length; ++i) {
            if (numbers[i] < numbers[i - 1]) {
                return numbers[i];
            }
        }
        return numbers[0];
    }
}

提交结果如下:

然后就是二分查找，不过因为有相同数字的存在，显得判断麻烦了点。需要根据中间数与左右两边数的大小关系决定下一步，如果三者相等就只好退化为线性查找了，而三者是递增关系的话就可以直接返回最左数字，否则说明左边数大于中间数（这时最小数只能在中间与右边数之间这一段）或中间数大于右边数（这时最小数只能在左边与中间数之间这一段）。时间复杂度为 $O (l o g n)$ （极端情况退化为 $O (n)$ ），空间复杂度为 $O (1)$ 。

JAVA版代码如下：

class Solution {
    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            if (left == right - 1) {
                return Math.min(numbers[left], numbers[right]);
            }
            int middle = left + (right - left) / 2;
            if (numbers[left] == numbers[middle] && numbers[middle] == numbers[right]) {
                for (int i = left + 1; i <= right; ++i) {
                    if (numbers[i] < numbers[i - 1]) {
                        return numbers[i];
                    }
                }
                return numbers[left];
            }
            if (numbers[left] <= numbers[middle] && numbers[middle] <= numbers[right]) {
                return numbers[left];
            }
            if (numbers[left] > numbers[middle]) {
                right = middle;
            }
            else {
                left = middle;
            }
        }
        return numbers[0];
    }
}

提交结果如下:

最后是分治法，根据中间数与右边数的大小关系缩小区间：

中间数大于右边数：说明最小数肯定在中间数到右边数之间，直接把左边界移动到当前中间数的位置；
中间数等于右边数：无法确定最小数在哪个区间，但可以肯定不会比右边数大，所以可以左移右边界；
中间数小于右边数：说明最小数肯定在左边数到中间数之间，直接把右边界移动到中间位置。

时间复杂度为 $O (l o g n)$ （极端情况退化为 $O (n)$ ，即所有数相等的情况），空间复杂度为 $O (1)$ 。

JAVA版代码如下：

class Solution {
    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            if (left == right - 1) {
                return Math.min(numbers[left], numbers[right]);
            }
            int middle = left + (right - left) / 2;
            if (numbers[middle] > numbers[right]) {
                left = middle;
            }
            else if (numbers[middle] < numbers[right]) {
                right = middle;
            }
            else {
                --right;
            }
        }
        return numbers[0];
    }
}

提交结果如下:

Python版代码如下：

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

提交结果如下: