ACM 选手图解 LeetCode 寻找旋转排序数组中的最小值

简介: ACM 选手图解 LeetCode 寻找旋转排序数组中的最小值

大家好呀,我是帅蛋。


今天解决寻找旋转排序数组中的最小值,这是二分查找的最后一道实战题。


真是最后一道,大家忍一下。

640.jpg

其实本来还有几道二分查找的题准备写的,但是看着大家对二分查找的兴趣好像不是很大,当然也可能是觉得太简单...


我也不准备写了...

640.jpg

话不多说,让我们快点完事。

640.png



   LeetCode 153:寻找旋转排序数组中的最小值



题意


已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次旋转后,得到输入数组。


例如:nums = [0,1,2,4,5,6,7] 旋转 4 次可以得到 [4,5,6,7,0,1,2]。


给你一个无重复元素的数组 nums,原来是一个升序数组,并按照上述情形做了多次旋转。


请你找出并返回数组中的最小元素。


示例


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

输出:1

解释:原数组为 [0,1,2,4,5,6,7],旋转 4 次得到输入数组。


提示


注意数组 [a[0],a[1],a[2],...,a[n-1]] 旋转一次的结果为数组 [a[n-1],a[0],a[1],...,a[n-2]]。


  • 1 <= n == len(nums) <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数互不相同
  • nums 原先是一个升序数组,并进行了 1 ~ n 次旋转


题目解析


难度中等,值得一搞。


其实关于旋转排序数组,我们已经做过两种类型的了:


ACM 选手图解 LeetCode 搜索旋转排序数组

ACM 选手图解 LeetCode 搜索旋转排序数组Ⅱ


Ⅰ是数组 nums 无重复元素,Ⅱ是数组 nums 存在重复元素。


本题旋转排序数组和 Ⅰ 是一种类型,数组 nums 无重复元素


但是本题又有不同,之前的题是给出一个 target,在 nums 中找是否存在 target,而本题是直接在旋转数组中找最小值


题虽不同,但是做法没有大的改变,无非就是维护一个最小值的指针,每次比较就更新当前的最小值


如果你吃透了前面两道旋转排序数组,这道题对你来说,应该是简单题


具体步骤如下:


  • 初始化一个最小值指针 nums_min。
  • 找出 mid,如果 nums[mid] < nums_min,更新 nums_min。
  • 如果左半区有序,维护 nums_min,范围缩小至[mid+1,high]。
  • 否则就找右半区,维护 nums_min,范围缩小至[low,mid-1]。


图解


[4,5,6,7,0,1,2] 为例。


首先初始化 low,high 及 nums_min 指针。

640.png

low, high = 0, len(nums) - 1
nums_min = float('inf')

第 1 步,low = 0,high = 6,mid = low + (high - low) // 2 = 3:

640.png

mid = low + (high - low) // 2


此时 nums_min = inf, nums[mid] < nums_min,所以维护最小值指针 nums_min 的值。

640.png

if nums[mid] < nums_min:
    nums_min = nums[mid]

当前 nums[low] < nums[mid],证明左区间有序。


nums_min > nums[low],维护最小值指针 nums_min,同时 low 向右移动至 mid + 1 处。

640.png


if nums[low] < nums[mid]:
    if nums_min > nums[low]:
        nums_min = nums[low]
    low = mid + 1

第 2 步,low = 4,high = 6,mid = low + (high - low) // 2 = 5:


640.png


此时 nums_min = 4, nums[mid] < nums_min,所以维护最小值指针 nums_min 的值。

640.png

当前 nums[low] < nums[mid],证明左区间有序。


nums_min > nums[low],维护最小值指针 nums_min,同时 low 向右移动至 mid + 1 处。

640.png


第 3low = 6,high = 6,mid = low + (high - low) // 2 = 6

640.png

此时 nums_min = 0, nums[mid] > nums_min。


并且 nums[low] >= nums[mid],证明右区间有序,nums_min < nums[high],high 指针向右移动至 mid - 1。

640.png

此时,high < low,循环结束,返回最小值 nums_min。


本题解使用二分查找,所以时间复杂度为 O(logn)


只是额外的维护了几个指针,所以空间复杂度为 O(1)


代码实现


Python 代码实现

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        low, high = 0, len(nums) - 1
        nums_min = float('inf')
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] < nums_min:
                nums_min = nums[mid]
            if nums[low] < nums[mid]:
                if nums_min > nums[low]:
                    nums_min = nums[low]
                low = mid + 1
            else:
                if nums_min > nums[high]:
                    nums_min = nums[high]
                high = mid - 1
        return nums_min


Java 代码实现


class Solution {
    public int findMin(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int low = 0;
        int high = nums.length - 1;
        int nums_min = 5001;
        while (low <= high){
            int mid = low + (high - low) / 2;
            if(nums[mid] < nums_min){
                nums_min = nums[mid];
            }
            if(nums[low] < nums[mid]){
                if(nums_min > nums[low]){
                    nums_min = nums[low];
                }
                low = mid + 1;
            }else{
                if(nums_min > nums[high]){
                    nums_min = nums[high];
                }
                high = mid - 1;
            }
        }
        return nums_min;
    }
}


图解寻找旋转排序数组中的最小值到这就结束辣,这也意味着现阶段的二分查找到这就结束了。


如果是认真跟下来的小宝贝肯定是收获满满,这点我还是很自信的。


640.jpg



还是那句话,总体来说呢,二分查找就是个事儿精,细节控,在用二分的时候一定要打起十二分精神


下面我们来开始新的专题,如果期待的话,记得给我三连:点赞 + 在看 + 转发


让我看到你!


640.jpg



我是帅蛋,我们下次见

相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
40 0
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
21 4
|
2月前
|
机器学习/深度学习
Leetcode第48题(旋转图像)
这篇文章介绍了LeetCode第48题“旋转图像”的解题方法,通过原地修改二维矩阵实现图像的顺时针旋转90度。
29 0
Leetcode第48题(旋转图像)
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
19 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
68 0
|
2月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
17 0
|
4月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
4月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2