【leetcode】25. 数组-旋转数组的最小数字

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目

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

示例 1：

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

示例 2：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

方法一

分析

首先，题目中给出的数组是部分有序。最小的元素就是旋转点：

  1. 前后元素都比他大
  2. 前边的子数组是递增的
  3. 后边的子数组是递增的

因此，直观的解法就是遍历，找到第一个位置：numbers[l] < numbers[r]。
时间复杂度：O(N)
空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int l = 0, r = numbers.size() - 1;
        while (l < r) {
            if (numbers[l] >= numbers[r]) {
                l++;
            } else {
                break;
            }
        }
        return numbers[l];
    }
};

方法二

分析

题意已经明确，原始数组是由有序数组旋转生成，设最小值的索引为mid，则[0, mid)和[mid, size)是两个有序数组。查找最小值本身就是搜索问题。本题题意抽取出如下两点：

  1. 有序
  2. 查找

因此，可以考虑二分搜索算法，判断条件如下;

  1. numbers[mid] > numbers , 则l = mid + 1
  2. numbers[mid] < numbers, 则r = mid
  3. numbers[mid] == numbers ,特殊的点就在这儿，此时，最小值只能在[l, r)，因此r--

时间复杂度：O(logN)
空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int l = 0, r = numbers.size() - 1;
        while (l < r) {
            int mid = ((r - l) >> 1) + l;
            if (numbers[mid] > numbers[r]) {
                l = mid + 1;
            } else if (numbers[mid] < numbers[r]) {
                r = mid;
            } else {
                r--;
            }
        }
        return numbers[r];
    }
};