11.旋转数组的最小数字 (Easy)*

题目描述*

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

示例*

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

输出：1

代码*

可以直接遍历。

或者用二分，从中间分为两半，一半是递增，另一半是旋转的，可以根据头尾结点的大小关系判断。还要考虑当 mid, r 结点值相同的情况，处理的方式有两种，相等时 r-- 舍弃右侧，或在开始预处理舍弃整个数组右侧的与头结点相等的结点。

遍历二分

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

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        // 预处理
        while(r > 0 && nums[r] == nums[l]) {
            r--;
        }
        while(l < r) {
            int mid = l + (r - l)/2;
            if(nums[mid] > nums[r]) {
                l = mid + 1;
            }else {
                r = mid;
            }
        }
        return nums[l];
    }
};

最后更新: July 23, 2022