欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指Offer 图解 | 寻找旋转排序数组中的最小值

程序员文章站 2022-06-03 14:14:08
...

点击上方蓝字设为星标剑指Offer 图解 | 寻找旋转排序数组中的最小值

下面开始今天的学习~

剑指Offer 图解 | 寻找旋转排序数组中的最小值

今天分享的题目来源于 LeetCode 上第 153 号问题:寻找旋转排序数组中的最小值。也是《剑指Offer》上的一道经典题。

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组  [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

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

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

题目解析

这道题目最简单粗暴的方式就是 直接遍历 整个数组来寻找,这个方法的时间复杂度为 O(N),空间复杂度为 O(1) 。

不过,这样来做的话完全没有利用到题目给出一个条件 旋转 。

事实上,可以考虑将时间复杂度从 O(n) 缩小到 O(lgn),这时候 二分查找法 就浮现在脑海。

当然,这里是 二分查找法 的一种变体。

更多有关二分查找法的文章点击这篇:一网打尽!二分查找解题模版与题型全面解析

二分的方法可以保证每次比较后,去掉数组中一半的元素。

这道题目中可以将 中点 与 终点 进行比较。

  • mid < end:最小值在左半部分。

  • mid > end:最小值在右半部分。

也就是说只需要把 mid 和 end 比较,mid < end 丢弃右半部分(更新 end = mid),mid > end 丢弃左半部分( 更新 start = mid + 1)。

直到 end 等于 start 时候结束就可以了。

补充:之所以这里 更新 start = mid + 1 而不是 start = mid 是因为存在一种特殊情况。当数组只剩两个元素的时候,mid = (start + end)/ 2mid 取的就是 start。然后如果此时 mid > end,会发现 start 的位置不会变化,出现 死循环。(可以通过以下动画加深理解)

动画描述

代码实现

//author:程序员吴师兄
//source:图解面试算法
class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            if (nums[low] < nums[high]) return nums[low];
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]){
               low = mid + 1; 
            } else{
               high = mid;
            } 
          }
        return nums[low];
    }
}

复杂度分析

  • 时间复杂度:和二分搜索一样 O(logN)

  • 空间复杂度:O(1)

相关题目推荐

  • LeetCode 33:搜索旋转排序数组

  • LeetCode 154:寻找旋转排序数组中的最小值 II

剑指Offer 图解 | 寻找旋转排序数组中的最小值