深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)

简介: 深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容,和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣!

欢迎订阅本专栏 或者关注公众号 数据分析螺丝钉 回复关键词 【学习资料】免费领取学习资料❤️❤️

在本篇文章中,我们将详细解读力扣第154题“寻找旋转排序数组中的最小值 II”。通过学习本篇文章,读者将掌握如何使用多种方法来解决这一问题,包括线性扫描法和二分查找法。每种方法都将配以详细的解释和ASCII图解,以便于理解。

问题描述

力扣第154题“寻找旋转排序数组中的最小值 II”描述如下:

已知一个长度为 n 的数组,其元素是由范围 [0, n-1] 内的整数构成,并且数组原本是严格递增排序的,但在某个未知的点上进行了旋转(例如,数组 [0, 1, 2, 4, 5, 6, 7] 可能变为 [4, 5, 6, 7, 0, 1, 2])。这次数组中允许重复元素。请你找出其中最小的元素。

示例 1:

输入: nums = [2, 2, 2, 0, 1]
输出: 0

示例 2:

输入: nums = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1]
输出: 1

解题思路

  1. 初步分析
  • 数组是旋转排序数组,并且包含重复元素,因此最小值会在旋转点附近。
  • 可以使用线性扫描法或改进的二分查找法来找到最小值。
  1. 多种解法
  • 线性扫描法:简单遍历数组,找到最小值。
  • 改进的二分查找法:处理重复元素,提高搜索效率。

线性扫描法

解法思路

线性扫描法是一种直接的方法,通过遍历数组中的每个元素,找到最小值。

步骤
  1. 初始化最小值为数组的第一个元素。
  2. 遍历数组中的每个元素,如果发现比当前最小值还小的元素,则更新最小值。
  3. 返回最小值。
代码实现
def findMinLinear(nums):
    min_val = nums[0]
    for num in nums:
        if num < min_val:
            min_val = num
    return min_val
# 测试案例
print(findMinLinear([2, 2, 2, 0, 1]))  # 输出: 0
print(findMinLinear([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1]))  # 输出: 1
ASCII图解
数组: [2, 2, 2, 0, 1]
遍历过程:
  初始最小值: 2
  比较2: 当前最小值仍为2
  比较2: 当前最小值仍为2
  比较0: 更新最小值为0
  比较1: 当前最小值为0
最终最小值: 0

改进的二分查找法

解法思路

改进的二分查找法利用数组的特性,通过不断缩小搜索范围,快速找到最小值。与标准二分查找法不同的是,需要处理重复元素的情况。

步骤
  1. 初始化左右指针 leftright,分别指向数组的起始和末尾。
  2. left <= right的条件下,进行循环:
  • 计算中间指针 mid
  • 比较mid位置的元素和right位置的元素:
  • 如果 mid 元素大于 right 元素,说明最小值在右半部分,调整 left
  • 如果 mid 元素小于 right 元素,说明最小值在左半部分,调整 right
  • 如果 mid 元素等于 right 元素,无法确定最小值的位置,调整 right
  1. 循环结束后,left 指针指向最小值。
代码实现
def findMinBinarySearch(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        # 比较 mid 和 right 的值
        if nums[mid] > nums[right]:
            left = mid + 1
        elif nums[mid] < nums[right]:
            right = mid
        else:
            right -= 1  # nums[mid] == nums[right] 的情况
    
    return nums[left]
# 测试案例
print(findMinBinarySearch([2, 2, 2, 0, 1]))  # 输出: 0
print(findMinBinarySearch([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1]))  # 输出: 1
ASCII图解
数组: [2, 2, 2, 0, 1]
初始状态: left = 0, right = 4
1. mid = (0 + 4) // 2 = 2
   nums[mid] = 2, nums[right] = 1
   2 > 1, 所以最小值在右半部分
   更新: left = 3
2. mid = (3 + 4) // 2 = 3
   nums[mid] = 0, nums[right] = 1
   0 < 1, 所以最小值在左半部分
   更新: right = 3
最终状态: left = 3, right = 3
最小值: nums[left] = 0

复杂度分析

  • 线性扫描法
  • 时间复杂度:O(N),其中 N 是数组的长度。
  • 空间复杂度:O(1),使用了常数空间来存储最小值。
  • 改进的二分查找法
  • 时间复杂度:O(log N) 最坏情况下可能退化为 O(N),因为存在重复元素时,可能每次只能排除一个元素。
  • 空间复杂度:O(1),使用了常数空间来存储左右指针和中间指针。

测试案例分析

  1. 测试案例 1
  • 输入: [2, 2, 2, 0, 1]
  • 输出: 0
  • 解释: 数组在 2 之后旋转,最小值 0 在旋转点之后。
  1. 测试案例 2
  • 输入: [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1]
  • 输出: 1
  • 解释: 数组在最后一个 2 之后旋转,最小值 1 在旋转点之后。

总结

本文详细解读了力扣第154题“寻找旋转排序数组中的最小值 II”,通过线性扫描法和改进的二分查找法两种不同的解法,帮助读者深入理解如何高效地解决这个问题。希望读者通过本文的学习,能够在力扣刷题的过程中更加得心应手。

参考资料

  • 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
  • 力扣官方题解

🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)

❤️❤️作者知识有限,如有错误,请各位大佬评论区批评指正,不胜感激❥(^_-)

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
19天前
|
索引
力扣随机一题 6/26 哈希表 数组 思维
力扣随机一题 6/26 哈希表 数组 思维
13 0
|
19天前
|
存储 算法 索引
力扣每日一题 6/24 模拟 数组 单调栈
力扣每日一题 6/24 模拟 数组 单调栈
9 0
|
19天前
力扣随机一题 哈希表 排序 数组
力扣随机一题 哈希表 排序 数组
10 1
|
19天前
|
存储 算法
力扣每日一题 6/20 数学+数组
力扣每日一题 6/20 数学+数组
15 1
|
7天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
15天前
2670.找出不同元素数目差数组-力扣(LeetCode)
2670.找出不同元素数目差数组-力扣(LeetCode)
6 0
|
19天前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
15 0
|
19天前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
18 0
|
19天前
力扣随机一题 6/28 数组/矩阵
力扣随机一题 6/28 数组/矩阵
15 0
|
19天前
|
存储 安全
力扣每日一题 6/21 数组
力扣每日一题 6/21 数组
9 0