【剑指 Offer 11. 旋转数组的最小数字】


来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

题目描述:

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [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

解题思路:

可参考:Krahets & 作者:jyd.与官方解题方法。
》》》》》注意题干的条件:它原来是一个升序排列的数组《《《《《《

在这里插入图片描述

  • 寻找最小元素即为寻找 右排序数组 的首个元素 nums[x] , 旋转点
  • 利用二分查找的思想可以解题:

左边界为 low,右边界为high,区间的中点为 mid,最小值就在该区间内。将中间的元素 numbers[mid] 与右边界元素numbers[high] 进行比较,可能会有以下的三种情况:

1.当nums[mid] < nums[ high ]时:mid一定在右排序数组中,即旋转点x一定在**[ low,mid]**闭区间内,因此执行 high = mid ,缩小区间范围;

2.**当nums[mid] > nums[ high ]时:mid 一定在左排序数组中,即旋转点x一定在[mid+1,high]**闭区间内,因此执行 low=mid+1

3.当nums[m] = nums[ high ]时:无法判断m在哪个排序数组中,即无法判断旋转点x在 [ low,mid ]还是[m+1,high]区间中。执行: high=high-1 缩小判断范围

  • i=j 时跳出二分循环,并返回 旋转点的值 nums[ low] 就是最小值
  • 图示:(只看顺序,自己捋顺逻辑)
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

代码:

c++


class Solution {
public:
    int minArray(vector<int>& numbers) {
        int low =0;
        int high = numbers.size()-1;
        while (low<high){
            int mid = (low+high)/2;
            if (numbers[mid] >numbers[high] ){
                low = mid+1;
            }
            
            else if (numbers[mid] < numbers[high] ){
                high=mid;
            }
            
            else high--;
        }
        return numbers[low];

    }
};

python


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

  • 复杂度分析:
  • 时间复杂度O(log2N):在特例情况下(例如[1,1,1,1,1]),会退化到O(N)。
  • 空间复杂度O(1):low,high,mid 变量使用常数大小的额外空间。
Logo

CSDN联合极客时间,共同打造面向开发者的精品内容学习社区,助力成长!

更多推荐