知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 03 - 寻找旋转排序数组中的最小值 ## 题目(LeetCode 153) 在一个旋转过的**无重复元素**的递增数组中找最小值。 ``` 输入:nums = [3, 4, 5, 1, 2] 输出:1 输入:nums = [4, 5, 6, 7, 0, 1, 2] 输出:0 输入:nums = [11, 13, 15, 17] 输出:11(没旋转,第一个就是最小) ``` 要求 O(log n) 时间。 ## 大白话理解 旋转数组 = 把递增数组的**前半段切下来拼到后面**。 ``` 原数组:[0, 1, 2, 4, 5, 6, 7] ↑ 最小值 = 0 旋转后:[4, 5, 6, 7, 0, 1, 2] └───大值区───┘ └─小值区─┘ ↑ 最小值 = 0 ``` 规律:旋转后最小值就是"断裂点"右边第一个元素。大值区全在小值区左边。 想象一个 L 形曲线:先高后低。我们要找的就是那个拐点(最低点)。 ``` 值 │ │ ● │ ● │ ● ● │ ● ● │ ● │ ← 最低点 └────────────────────→ 下标 ``` ## 核心思路:跟 nums[r] 比较 用 `nums[mid]` 和 `nums[r]` 比较,判断 mid 在大值区还是小值区。 ``` 如果 nums[mid] > nums[r]: mid 在大值区,最小值一定在 mid 右边 → l = mid + 1 如果 nums[mid] <= nums[r]: mid 在小值区,最小值可能是 mid 或在 mid 左边 → r = mid(不能 mid-1,因为 mid 可能就是最小值!) ``` ``` 为什么跟 nums[r] 比较? [4, 5, 6, 7, 0, 1, 2] l mid r 7 > 2 → mid 在大值区 [7, 0, 1, 2, 4, 5, 6] l mid r 1 < 6 → mid 在小值区 跟 nums[r] 比较能直接判断 mid 在哪一侧。 ``` ## 代码 ```java public int findMin(int[] nums) { int l = 0, r = nums.length - 1; while (l < r) { // 注意:这里是 l < r,不是 l <= r int mid = l + (r - l) / 2; if (nums[mid] > nums[r]) { // mid 在大值区 → 最小值在 mid 右边 l = mid + 1; } else { // mid 在小值区 → 最小值是 mid 或在 mid 左边 r = mid; // 不能 mid-1,mid 可能就是答案 } } // 退出时 l == r,指向最小值 return nums[l]; } ``` > 💬 **Q:为什么用 `while(l < r)` 而不是 `while(l <= r)`?** > > 因为当 `l == r` 时,区间只剩一个元素,它就是答案。如果用 `while(l <= r)`: > - `nums[mid] <= nums[r]` 时执行 `r = mid`,但 mid = l = r,永远不缩小区间 → 死循环 > > 对比标准二分:标准二分用 `mid + 1` 和 `mid - 1` 缩小区间,所以能用 `while(l <= r)`。但这里用 `r = mid`(不跳过),所以必须用 `while(l < r)`。 ## 过程模拟 ### 场景1:标准旋转数组 ``` nums = [3, 4, 5, 1, 2] 第1轮: l=0, r=4, mid=2 nums[2]=5, nums[4]=2 → 5 > 2 → mid 在大值区 → l = mid + 1 = 3 [3, 4, 5, 1, 2] └─大值─┘ └小值┘ ↑ l=3 第2轮: l=3, r=4, mid=3 nums[3]=1, nums[4]=2 → 1 <= 2 → mid 在小值区 → r = mid = 3 第3轮: l=3, r=3 → l < r 不成立,退出 nums[3] = 1 → 答案 ✓ ``` ### 场景2:没旋转(完全有序) ``` nums = [11, 13, 15, 17] 第1轮: l=0, r=3, mid=1 nums[1]=13, nums[3]=17 → 13 <= 17 → mid 在小值区 → r = mid = 1 第2轮: l=0, r=1, mid=0 nums[0]=11, nums[1]=13 → 11 <= 13 → mid 在小值区 → r = mid = 0 第3轮: l=0, r=0 → 退出 nums[0] = 11 → 答案 ✓ ``` ### 场景3:旋转点在最右 ``` nums = [2, 3, 4, 5, 1] 第1轮: l=0, r=4, mid=2 nums[2]=4, nums[4]=1 → 4 > 1 → mid 在大值区 → l = 3 第2轮: l=3, r=4, mid=3 nums[3]=5, nums[4]=1 → 5 > 1 → mid 在大值区 → l = 4 第3轮: l=4, r=4 → 退出 nums[4] = 1 → 答案 ✓ ``` ## 复杂度 - 时间:O(log n),每次区间减半 - 空间:O(1) ## 一句话总结 跟 `nums[r]` 比较判断 mid 在大值区还是小值区:`nums[mid] > nums[r]` 就去右边,否则去左边。`r = mid` 保证不跳过答案。 --- 上一篇:[02 - 搜索旋转排序数组](./02-search-rotated.md) | 下一篇:[04 - 在排序数组中查找第一个和最后一个位置](./04-first-and-last.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入