当前位置：网站首页>【每日一题】【leetcode】25. 数组-旋转数组的最小数字

【每日一题】【leetcode】25. 数组-旋转数组的最小数字

2022-08-10 15:04:00 【aneutron】

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

方法一

分析

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

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

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

代码

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)是两个有序数组。查找最小值本身就是搜索问题。本题题意抽取出如下两点：

有序
查找

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

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

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

代码

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];
    }
};

原网站

版权声明
本文为[aneutron]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2069614