❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
在本篇文章中，我们将详细解读力扣第153题“寻找旋转排序数组中的最小值”。通过学习本篇文章，读者将掌握如何使用多种方法来解决这一问题，包括线性扫描法和二分查找法。每种方法都将配以详细的解释和ASCII图解，以便于理解。
问题描述
力扣第153题“寻找旋转排序数组中的最小值”描述如下：
已知一个长度为
n的数组，其元素是由范围[0, n-1]内的整数构成，并且数组原本是严格递增排序的，但在某个未知的点上进行了旋转（例如，数组[0, 1, 2, 4, 5, 6, 7]可能变为[4, 5, 6, 7, 0, 1, 2]）。请你找出其中最小的元素。
示例 1:
输入: nums = [3, 4, 5, 1, 2] 输出: 1
示例 2:
输入: nums = [4, 5, 6, 7, 0, 1, 2] 输出: 0
示例 3:
输入: nums = [11, 13, 15, 17] 输出: 11
解题思路
- 初步分析：
- 数组是旋转排序数组，因此最小值会在旋转点附近。
- 可以使用线性扫描法或二分查找法来找到最小值。
- 多种解法：
- 线性扫描法：简单遍历数组，找到最小值。
- 二分查找法：使用二分查找来高效地找到最小值。
线性扫描法
解法思路
线性扫描法是一种直接的方法，通过遍历数组中的每个元素，找到最小值。
步骤
- 初始化最小值为数组的第一个元素。
- 遍历数组中的每个元素，如果发现比当前最小值还小的元素，则更新最小值。
- 返回最小值。
代码实现
def findMinLinear(nums): min_val = nums[0] for num in nums: if num < min_val: min_val = num return min_val # 测试案例 print(findMinLinear([3, 4, 5, 1, 2])) # 输出: 1 print(findMinLinear([4, 5, 6, 7, 0, 1, 2])) # 输出: 0 print(findMinLinear([11, 13, 15, 17])) # 输出: 11
ASCII图解
数组: [4, 5, 6, 7, 0, 1, 2] 遍历过程: 初始最小值: 4 比较5: 当前最小值仍为4 比较6: 当前最小值仍为4 比较7: 当前最小值仍为4 比较0: 更新最小值为0 比较1: 当前最小值为0 比较2: 当前最小值为0 最终最小值: 0
二分查找法
解法思路
二分查找法利用数组的特性，通过不断缩小搜索范围，快速找到最小值。
步骤
- 初始化左右指针
left和right，分别指向数组的起始和末尾。 - 在
left <= right的条件下，进行循环：
- 计算中间指针
mid。 - 比较
mid位置的元素和right位置的元素：
- 如果
mid元素大于right元素，说明最小值在右半部分，调整left。 - 否则，说明最小值在左半部分，调整
right。
- 循环结束后，
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 else: right = mid return nums[left] # 测试案例 print(findMinBinarySearch([3, 4, 5, 1, 2])) # 输出: 1 print(findMinBinarySearch([4, 5, 6, 7, 0, 1, 2])) # 输出: 0 print(findMinBinarySearch([11, 13, 15, 17])) # 输出: 11
ASCII图解
数组: [4, 5, 6, 7, 0, 1, 2] 初始状态: left = 0, right = 6 1. mid = (0 + 6) // 2 = 3 nums[mid] = 7, nums[right] = 2 7 > 2, 所以最小值在右半部分 更新: left = 4 2. mid = (4 + 6) // 2 = 5 nums[mid] = 1, nums[right] = 2 1 < 2, 所以最小值在左半部分 更新: right = 5 3. mid = (4 + 5) // 2 = 4 nums[mid] = 0, nums[right] = 1 0 < 1, 所以最小值在左半部分 更新: right = 4 最终状态: left = 4, right = 4 最小值: nums[left] = 0
复杂度分析
- 线性扫描法：
- 时间复杂度：O(N)，其中 N 是数组的长度。
- 空间复杂度：O(1)，使用了常数空间来存储最小值。
- 二分查找法：
- 时间复杂度：O(log N)，其中 N 是数组的长度。二分查找的时间复杂度为 O(log N)。
- 空间复杂度：O(1)，使用了常数空间来存储左右指针和中间指针。
测试案例分析
- 测试案例 1：
- 输入:
[3, 4, 5, 1, 2] - 输出:
1 - 解释: 数组在
4之后旋转，最小值1在旋转点之后。
- 测试案例 2：
- 输入:
[4, 5, 6, 7, 0, 1, 2] - 输出:
0 - 解释: 数组在
7之后旋转，最小值0在旋转点之后。
- 测试案例 3：
- 输入:
[11, 13, 15, 17] - 输出:
11 - 解释: 数组没有旋转，最小值为第一个元素。
总结
本文详细解读了力扣第153题“寻找旋转排序数组中的最小值”，通过线性扫描法和二分查找法两种不同的解法，帮助读者深入理解如何高效地解决这个问题。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。
参考资料
- 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- 力扣官方题解
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️作者知识有限，如有错误，请各位大佬评论区批评指正，不胜感激❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
