LeetCode 1064. 不动点
题目描述
题意分析
在一个严格递增的整数数组中，寻找满足
arr[i] == i的最小下标i。这里下标从零开始，返回的是位置；若不存在这样的元素，返回-1。严格递增表示元素互不相同，但不动点仍可能有多个，因此找到任意一个还不够，必须继续确定最左的位置。数组中的值可以为负，答案仍按下标而非数值大小选择。
解法：二分查找左边界
核心思路
[!blue]
虽然要比较的是元素与它自己的下标，而不是固定目标值，但可以考虑差值
f(i) = arr[i] - i。由于数组是严格递增的整数数组，相邻值至少增加一，因此f(i + 1) - f(i) = arr[i + 1] - arr[i] - 1 >= 0，这个差值序列单调不减。不动点对应差值为零的位置。单调差值会先小于零，再可能出现一段零，最后大于零；所以先查找第一个满足
arr[i] >= i的位置，再验证是否恰好相等，就能得到最左不动点。代码直接比较值与下标，不需要真的创建差值数组。使用半开区间边界
left = 0、right = n。若arr[mid] < mid，单调性保证mid及左边的差值都小于零，可以令left = mid + 1；否则当前点已满足非负条件，将right = mid，继续向左收紧边界。即使已经相等，也不能提前返回。搜索中，小于
left的位置都已确定不满足非负条件；当right < n时，它是已知满足条件的上界。循环结束，两者收敛到第一个可能非负的位置。若它等于n，说明整个数组都未达到边界；若值严格大于下标，说明差值从负数直接跳过了零，也没有答案。因此最后必须同时检查下标有效与
arr[left] == left，不能把非负边界直接当作不动点。
解题步骤
- 初始化
left = 0、right = arr.length。- 在
left < right时取中点，若arr[mid] < mid就移动左边界，否则收缩右边界。- 收敛后检查
left < n，避免读取不存在的位置。- 值恰好等于下标时返回
left，否则返回-1。
代码实现
class Solution {
public int fixedPoint(int[] arr) {
int left = 0;
// 半开区间查找第一个满足 arr[i] >= i 的位置。
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < mid) {
left = mid + 1;
} else {
right = mid;
}
}
// 找到的是大于等于的边界，还要验证下标有效且恰好相等。
return left < arr.length && arr[left] == left ? left : -1;
}
}
func fixedPoint(arr []int) int {
// 半开区间查找第一个满足 arr[i] >= i 的位置。
left, right := 0, len(arr)
for left < right {
mid := left + (right-left)/2
if arr[mid] < mid {
left = mid + 1
} else {
right = mid
}
}
// 找到的是大于等于的边界，还要验证下标有效且恰好相等。
if left < len(arr) && arr[left] == left {
return left
}
return -1
}
复杂度分析
- 时间复杂度：$O(\log(n + 1))$，每轮将待查范围缩小约一半。
- 空间复杂度：$O(1)$，只保存两个边界和中点。
关键点总结
[!green]
- 严格递增且元素为整数，保证元素减下标的差值单调不减。
- 二分寻找的是第一个非负差值，最后还要判断是否为零。
- 相等时继续收缩右边界，才能满足返回最小下标的要求。
易错点总结
[!yellow]
- 遇到相等就返回，只能保证某个不动点，不能保证是最左的。
- 直接返回二分位置，可能返回值大于下标的位置，或者数组末尾之后的
n。- 允许重复元素时仍套用同一单调性推导，相邻值不增加会使差值下降，二分依据不再成立。
- 将半开区间的
right = n与闭区间的循环或更新规则混用，会造成越界或漏查。- 返回
arr[left]虽然在命中时数值相同，但必须先验证命中，不能把任意边界值当成所求下标。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 08.03. 魔术索引 | 简单 | 原题允许重复值，a[i]-i不再保证单调，本题严格递增数组可直接利用这一单调量二分。 |
| 35. 搜索插入位置 | 简单 | 同样查找单调边界，本题比较a[i]与i，而非与固定目标值比较。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！