LeetCode算法日记 - Day 12: 寻找旋转排序数组中的最小值、点名
目录
1. 寻找旋转排序数组中的最小值
1.1 题目分析
1.2 解法
1.3 代码实现
2. 点名
2.1 题目解析
2.2 解法
2.3 代码实现
1. 寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
1.1 题目分析
这道题是典型的 旋转排序数组查找元素 问题。
原数组是一个严格升序、元素互不相同的数组，但在某个未知位置 k 进行了旋转（相当于把前面的一段移到末尾）。旋转后，整体仍保持了“两段有序”的特性。
举例：
原数组: [0, 1, 2, 4, 5, 6, 7] 旋转后: [4, 5, 6, 7, 0, 1, 2] // k = 3我们需要在 O(log n) 时间内查找 target 所在的下标，否则返回 -1。
显然这是一个二分查找的应用题，但与普通二分不同的是，旋转导致数组整体不再是单调的。
全局观察：
-
数组依然由两段单调递增的子数组组成。
-
旋转点（最小值位置）将数组分为 [A, B] 和 [C, D] 两段。
-
由于是严格递增，左段所有值都大于右段的所有值。
-
因此，此，通过对比 mid 与数组某个固定位置（如 nums[right]）的大小，可以判断 mid 在哪一段。
特别注意边界情况：
-
当 [C, D] 区间只有一个元素时，C 的值可能等于 D 的值（最后一次迭代时出现）。
-
所以判断条件中可能出现 “小于等于” 的情况，而不是单纯的“小于”。
结论：
通过比较 nums[mid] 和 nums[right]，我们可以将查找区间一分为二：
-
若nums[mid] > nums[right] → mid 在左段 [A, B]，最小值在右边，left = mid + 1
-
若nums[mid] <= nums[right] → mid 在右段 [C, D]，最小值在左边，right = mid
利用这个方法可以先找到旋转点，然后再在有序的一段中二分查找目标值，从而在 O(log n) 时间内完成查找。
-
参照物固定且
mid可能是答案 → 用等号保留（<= / >=） -
参照物动态且比较结果能排除 mid → 不用等号（< / >）
1.2 解法
i）初始化指针
-
left = 0
-
right = nums.length - 1
-
固定参照值 x = nums[right]（最后一个元素）
ii）二分查找
-
当 left < right 时：
-
计算中点 mid = left + (right - left) / 2
-
若 nums[mid] > x：说明 mid 在左半段，最小值在 mid + 1 ~ right，更新 left = mid + 1
-
否则：说明 mid 在右半段（可能是最小值）更新 right = mid
-
iii）结束条件
-
当 left == right 时，循环退出，此时 nums[left] 就是最小
iiii）返回结果
-
返回 nums[left]
1.3 代码实现
class Solution {public int findMin(int[] nums) {int left = 0, right = nums.length-1,n=nums.length-1;while(left<right){int mid = left + (right-left)/2;if(nums[mid] <= nums[n]){right = mid;}else{left = mid + 1;}}return nums[left];}
}2. 点名
LCR 173. 点名 - 力扣（LeetCode）
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
示例 1：
输入：records = [0,1,2,3,5] 输出：4
示例 2：
输入：records = [0, 1, 2, 3, 4, 5, 6, 8] 输出：7
提示：
1 <= records.length <= 10000
2.1 题目解析
这道题是一个 有序数组查找缺失元素 的经典问题。数组长度为 n-1，且所有数字都在 0 ~ n-1 范围内，只有一个数字缺失。
由于数组是严格递增且元素唯一，可以利用数组下标与数值的关系来快速定位缺失值。
全局规律：
-
在缺失数字的左边，nums[i] == i（值与下标相等）
-
在缺失数字及其右边，nums[i] != i（值与下标不等）
示例：
nums = [0, 1, 2, 4, 5]
索引: 0 1 2 3 4
规律:0=0 1=1 2=2 ❌4!=3
缺失数字: 3
关键突破口：
利用这个“左边相等、右边不等”的二段性，通过 二分查找 可以在 O(log n) 时间内定位缺失位置。
2.2 解法
初始化
-
left = 0
-
right = nums.length - 1
二分查找逻辑
-
计算 mid = left + (right - left) / 2
-
如果 nums[mid] == mid
→ 缺失数字在右边，left = mid + 1 -
否则
→ 缺失数字在左边或正好在 mid 处，right = mid
结束条件
-
循环结束时，left == right，指向缺失数字应在的位置
返回结果
-
如果 nums[left] == left，缺失数字是 left + 1
-
否则缺失数字是 left
2.3 代码实现
class Solution {public int missingNumber(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] == mid) {left = mid + 1;} else {right = mid;}}return left == nums[left] ? left + 1 : left;}
}