今天分享的题目来源于 LeetCode 第 154 号问题:寻找旋转排序数组中的最小值 II。

题目链接:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

一、题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [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

二、题目解析

这道题最直观的解法是 从头到尾遍历数组一次,轻轻松松就能找出最小的元素。

这种思路的时间复杂度显然是 O(n)

很显然,这种做法 没有利用输入的旋转数组的特性,所以在面试环节面试官肯定会问你:还能优化一下吗?

一般的,O(n) 复杂度的优化我们都是往 二分查找 这个思路上去考虑的。

设置 start, end 指针分别指向 numbers 数组左右两端,取它们的中点 mid = (start + end ) / 2,然后将 numbers[mid]numbers[end] 进行对比:

1、当 numbers[mid] > numbers[end]

此时,mid 在 左排序数组 中,而旋转点 x 一定在 [ mid + 1,end ] 闭区间内,所以接下来的操作是在 [ mid + 1,end ] 区间内寻找旋转点,相应的,改变 start 的值为 mid + 1。

2、numbers[mid] < numbers[end]

此时,mid 在 右排序数组 中,而旋转点 x 一定在 [ start,mid ] 闭区间内,所以接下来的操作是在 [ start,mid ] 区间内寻找旋转点,相应的,改变 end 的值为 mid 。

3、numbers[mid] = numbers[end]

三、动画描述

隐藏内容
本内容需权限查看
  • 普通: 5积分
  • 会员: 免费
  • 算法训练营永久会员: 免费

四、图片描述



五、参考代码

class Solution {
    public int minArray(int[] numbers) {
        //设置 start, end 指针分别指向 numbers 数组左右两端
        int start = 0, end = numbers.length - 1;

        //循环判断处理,直到找到结果
        while (start < end) {

            // mid 为中点(这里向下取整,比如 ( 2 + 7 )/ 2 = 4 )
            int mid = (start + end) / 2;

            //当 mid 点所在元素大于数组末端的元素时,这意味着 [start , mid] 是有序的数组
            if (numbers[mid] > numbers[end]){

                // 所以旋转点在 [ mid + 1, end ] 区间里面 ,更新 start 的位置为 mid + 1
                start = mid + 1;

            }else if (numbers[mid] < numbers[end]){

                // 当 mid 点所在元素小于数组开始端的元素时,这意味着 [mid , end] 是有序的数组
                // 所以旋转点在 [ start, mid ] 区间里面 ,更新 end 的位置为 mid 
                end = mid;

                //思考题?:为什么 start 是更新为 mid + 1,而 end 却是更新为 mid

            }else{

                //此时,出现了 numbers[mid] = numbers[end] 的情况,无法判断 
                //    [ start , mid ]  为有序数组区间
                //  还是  [ mid , end ]  为有序数组区间
                //  比如: [1, 0, 1, 1, 1] 和  [1, 1, 1, 0, 1]
                //  所以这里采取遍历的方式
                return findMin(numbers,start,end);

            }
        }
        return numbers[start];
    }

     public int findMin(int[] numbers,int start,int end){

        int result = numbers[start];

        for(int i = start;i <= end;i++){

            if (numbers[i] < result) {
                result = numbers[i];
            }
        }
        return result;
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(log2N)。

空间复杂度

空间复杂度为 O(1)。

七、相关标签

  • 二分查找
  • 数组
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。