LeetCode 1064. 不动点

约 6 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 京东
标签
数组 二分查找
目录

题目描述

✅ 1064. 不动点

题意分析

给一个按升序排列且元素互不相同的整数数组 arr，返回最小的下标 i，使得 arr[i] == i；不存在这样的下标就返回 -1。

两个词是解法的全部来源。第一是「最小的」——答案可能有多个，必须取最靠左的那个，这决定了二分不能一命中就返回，而要继续向左收缩。第二是「升序且互不相同」，也就是严格递增。严格递增比单纯的非递减强得多，它带来一条至关重要的性质：

令 f(i) = arr[i] - i。因为 arr 严格递增且都是整数，必有 arr[i + 1] ≥ arr[i] + 1，两边同减 i + 1 得 f(i + 1) ≥ f(i)。所以 f 是单调不减的。 而不动点恰好是 f(i) == 0 的位置。单调 + 找零点 = 可以二分。

这条推导也划出了适用边界：如果数组只是非递减、允许重复（例如 [-1, 0, 0, 2]，f 为 -1, -1, -2, -1 并不单调），上面的性质立刻失效，只能线性扫描。题目特意写明「互不相同」，就是在给二分开绿灯。

约束是 1 ≤ arr.length < 10^4，元素范围 [-10^9, 10^9]。数组不长，$O(n)$ 的线性扫描其实也能过——所以这题真正考的不是能不能做出来，而是能否说清为什么可以二分。

边界：可能一个不动点都没有（全部返回 -1）；不动点可能出现在下标 0 或末尾；因为 f 单调不减，取值为 0 的下标一定构成一段连续区间，「最小的那个」就是这段区间的左端点。

解法：二分查找左边界

核心思路

线性扫描能直接找到第一个 arr[i] == i，但题目的“升序且元素互不相同”还能支持二分。

定义 f(i) = arr[i] - i。因为数组由互不相同的整数严格递增，必有 arr[i + 1] ≥ arr[i] + 1，所以

f(i + 1) = arr[i + 1] - (i + 1) ≥ arr[i] - i = f(i)。

因此 f 单调不减，不动点就是 f(i) == 0 的位置。为了取得最小下标，可以先用二分找到第一个 f(i) ≥ 0 的位置，再检查该位置是否恰好等于 0。

使用左闭右开的搜索区间 [left, right)，维护两个不变量：

  • [0, left) 中所有位置都满足 arr[i] < i；
  • [right, n) 中所有位置都满足 arr[i] ≥ i。

若 arr[mid] < mid，由单调性可知 mid 及其左侧都不可能是第一个非负位置，令 left = mid + 1；否则 mid 可能就是边界，令 right = mid 保留它。循环结束时 left == right，该位置就是第一个满足 arr[i] ≥ i 的下标，若此处不相等，则整个数组不存在不动点。

正确性：二分不变量保证循环结束前没有遗漏第一个 f(i) ≥ 0 的位置。该位置之前的 f 全为负；如果该位置的 f 为 0，它自然是最小不动点；如果大于 0，由单调性知后面的 f 也都大于等于它，不可能再出现 0，所以返回 -1 正确。

解题步骤

  1. 初始化半开区间 [left, right) = [0, n)。
  2. 取 mid = left + (right - left) / 2，直接比较 arr[mid] 与 mid，避免先做减法。
  3. 若 arr[mid] < mid，令 left = mid + 1；否则令 right = mid，继续向左寻找边界。
  4. 循环结束后，只有 left < n && arr[left] == left 时返回 left，否则返回 -1。

对 arr = [0,1,2,4,5]，f = [0,0,0,1,1]。二分寻找第一个非负位置，边界最终收缩到 0，而不是在中途命中的 2 直接返回，因此答案是最小不动点 0。

对 arr = [1,2,3]，第一个 arr[i] ≥ i 的位置是 0，但 arr[0] != 0；此时 f(0) > 0，后面也不可能出现 0，正确返回 -1。单元素 [0]、答案在末尾的 [-10,-5,-1,3] 也由相同边界模板处理。

代码实现

class Solution {
    public int fixedPoint(int[] arr) {
        int left = 0;
        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 {
	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)$，每轮都将候选区间至少缩小一半。
  • 空间复杂度：$O(1)$，只使用左右边界和中点三个标量。

关键点总结

  • 可二分的真正依据是 f(i) = arr[i] - i 单调不减，而该性质依赖数组由互不相同的整数严格递增。
  • 把目标改写为“第一个 f(i) ≥ 0”后，可以直接套用半开区间的 lower bound 模板。
  • 找到边界后必须验证 arr[left] == left；lower bound 只保证大于等于 0，不保证等于 0。
  • 比较时写 arr[mid] < mid，无需真的计算 arr[mid] - mid，也避免把模板迁移到更大值域时发生减法溢出。

易错点总结

  • 命中就返回：arr = [0,1,2,4,5] 的中点可能先命中 2，但最小不动点是 0；命中后仍要向左寻找边界。
  • 省略最终相等检查：arr = [1,2,3] 的 lower bound 是 0，却不存在不动点；直接返回 left 会错误返回 0。
  • 混用区间模板：这里搜索区间是 [left, right)，所以初始 right = n、循环条件是 left < right、保留中点时写 right = mid；与闭区间模板混用容易漏解或死循环。
  • arr[mid] < mid 时向左收缩：此时 f(mid) < 0，零点只可能在右侧，应执行 left = mid + 1。
  • 数组允许重复时仍套用二分：变体 arr = [0,0,0,0] 中 f 不再单调，该算法会一路向右并漏掉下标 0。没有“元素互不相同”的保证时应线性扫描。
  • 忘记边界可能等于 n：当所有位置都满足 arr[i] < i 时，搜索结果为 n；访问 arr[left] 前必须先判断 left < n。

相似题目

题目 难度 考察点
704. 二分查找 简单 目标值唯一，命中即可返回，是本题去掉「找最左」要求后的基础形态
34. 在排序数组中查找元素的第一个和最后一个位置 中等 同时要找左右边界，需要写两次方向相反的收缩，最能巩固本题的写法
35. 搜索插入位置 简单 找的是「第一个大于等于目标的位置」，未命中时也要返回有意义的下标
278. 第一个错误的版本 简单 判定函数由外部 API 提供，最能体现「二分只需要单调判定，不需要有序数组」
剑指 Offer 53 - II. 0～n-1中缺失的数字 简单 同样把 arr[i] 与 i 比较，但找的是第一个不相等的位置，与本题恰好互补
852. 山脉数组的峰顶索引 中等 数组本身不单调，但「是否位于上升段」这个判定单调，是二分适用条件的最好例证
540. 有序数组中的单一元素 中等 靠下标奇偶性构造单调判定，展示了如何把非显然的问题改写成可二分的形式