旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

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

示例 2：

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

题目链接

Leetcode

题目解答

解法一

顺序查找，通过观察可以发现数组旋转之后，最小元素所在的位置刚好是元素数值递减的第一个位置，所以我们只需要遍历数组找到第一个递减的元素返回即可，如果数组遍历完都没有找到递减的元素，就返回数组的首元素。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

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

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.1 MB, 在所有 Java 提交中击败了90.30%的用户

解法二

二分查找，定义左端点left，右端点right，以及中间点mid，比较中间点和右端点对应数组元素值的大小，我们的目标是要找到最小值。当右端点对应的值更大时，最小值的范围是在中间点的左侧，所以把右端点移动到中间点位置，当中间点对应的值更大时，最小值的范围是在中间点的右侧，所以把左端点移动到中间点的下一个位置，当中间点和右端点对应的值相等时，即数组中的元素重复，此时把右端点左移一位。左右端点相遇的时侯，左端点对应的值就是旋转数组的最小数字。

时间复杂度:$O(\log{}n)$ 空间复杂度:$O(1)$

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

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.3 MB, 在所有 Java 提交中击败了46.47%的用户