算法面试：如何用二分查找第 k 个缺失正整数？

面试官考察点

题目表面是数组计数，核心是把“到位置 i 为止缺了多少个数”写成单调谓词，再把第 k 个缺失值转成边界搜索。LeetCode 1539 给出严格递增正整数数组和第 k 个缺失值的公开题面，并提供 Amazon 题组入口；Amazon SDE 指引强调可运行、健壮、经过测试的代码和边界检查。题面来源说明准备价值，不代表任何公司固定面试频率。

• 能否先写出 missing(i) = arr[i] - i - 1。
• 能否证明缺失数量随 i 单调不减。
• 能否正确处理答案在最后一个元素之后。
• 能否比较线性、二分与计数生成三种方案的适用边界。

30 秒回答框架

先说明数组从 0 下标开始。位置 i 前包含 arr[i] 个正整数，实际出现 i+1 个，因此缺失数量为 arr[i] - i - 1。对最小下标做二分，寻找第一个满足 missing(i) >= k 的位置 i。如果找到该位置，答案是 k 加上它前面已有的 i 个数组元素，即 k + i；如果整个数组缺失数都小于 k，答案在数组末尾之后，直接返回 k + n。扫描是 O(n)，二分是 O(log n)，额外空间 O(1)。

回答前需要澄清的问题

1. 数组是否保证严格递增且只包含正整数？若不保证，需要先排序或去重，复杂度会改变。
2. k 是否为正整数，是否可能大于数组长度或整数范围？
3. 只需要一个第 k 个值，还是要返回所有缺失值？后者不应强行使用二分。
4. 输入是否可能有超大整数，语言中的加法和索引是否会溢出？
5. 是否要求原数组不修改？二分方案本身不修改数组。

分步骤深入解答

第一步：建立缺失数量公式

如果数组完全连续，arr[i] 应该等于 i + 1。实际值比期望值多出的部分，就是 [1, arr[i]] 中缺失的正整数数量：

missing(i) = arr[i] - (i + 1)
           = arr[i] - i - 1

例如 arr = [2, 3, 4, 7, 11]，在 i=3 时，missing(3) = 7 - 3 - 1 = 3，缺失的是 1、5、6。

第二步：利用单调性定位边界

数组严格递增，所以 arr[i+1] >= arr[i] + 1。因此 missing(i+1) >= missing(i)，缺失数量不会下降。二分寻找第一个 missing(i) >= k 的位置；这个位置左边缺失不足 k，位置本身及右侧至少包含 k 个缺失值。

第三步：从边界反推答案

设边界为 i。i 左侧有 i 个数组元素，且这些元素之前的缺失数量小于 k。答案等于 k 加上需要跨过的 i 个已出现元素：k + i。若边界不存在，整个数组最后的缺失数量仍小于 k，答案在数组后方，n 个数组元素都要跨过，所以是 k + n。

第四步：给出二分实现

function findKthPositive(arr: number[], k: number): number {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const missing = arr[mid] - mid - 1;
    if (missing < k) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return k + left;
}

这里 right 取 n，表示允许边界落在数组末尾之后。循环结束时 left 是第一个缺失数达到 k 的位置，统一返回 k + left，无需写特殊分支。

第五步：证明复杂度与测试边界

每次二分把搜索区间缩半，时间复杂度 O(log n)，只使用常数变量。测试应包括 arr = [1,2,3,4], k = 2 得到 6，arr = [2,3,4,7,11], k = 5 得到 9，缺失从 1 开始、数组末尾连续、k=1，以及单元素数组。还应验证公式不依赖具体语言的整数下标细节。

高质量示范回答

我会先定义在下标 i 处已经缺了多少个正整数：arr[i] - i - 1。因为数组严格递增，这个数量单调不减，所以可以二分寻找第一个缺失数不少于 k 的位置。若边界是 i，前面有 i 个已出现元素，因此第 k 个缺失值是 k + i；把右边界设为 n，就能自然处理答案在数组最大值之后的情况。

实现使用半开区间 [left, right)。当 missing(mid) 小于 k 时，边界一定在右侧；否则收缩到 mid。循环结束返回 k + left。复杂度是 O(log n) 时间和 O(1) 空间。最后用首项缺失、尾部缺失、连续数组、单元素和多个 k 值测试，并与线性扫描结果对拍。

常见错误

• 把缺失数量写成 arr[i] - i，少减了 1。
• 二分寻找最后一个小于 k 的位置，却忘记把答案公式改成对应边界。
• 把 right 设为 n - 1，导致答案在数组末尾之后时需要额外分支且容易越界。
• 数组不满足严格递增时仍直接套公式。
• 只测题面样例，没有测试 [1,2,3]、[2] 和尾部连续等边界。
• 声称二分一定比扫描快，却不说明 n 很小时的常数开销和输入是否已排序。

实现取舍

根据数据规模与边界要求选择线性扫描或二分方案，并用测试验证不变量。

追问及应对

为什么缺失数量是单调的？

严格递增保证下一个元素至少比前一个大 1。下标增加 1 时，实际值增加至少 1，所以 arr[i] - i - 1 不会下降。

如果数组未排序或有重复值怎么办？

先按题目新契约处理：排序、去重并确认只保留正整数。排序成本至少 O(n log n)，去重后再使用同一个缺失数量公式；不能把原题的 O(log n) 结论直接带到未排序输入。

什么时候线性扫描更合适？

数组很短、只需一次答案，或输入来自流且无法随机访问时，扫描更简单。面试中应说明二分依赖已排序数组和 O(1) 随机访问。

如何返回前 k 个缺失值？

先用边界公式找到值域起点，再按数组指针和当前候选值线性生成，输出本身就需要 O(k) 时间；不能把输出成本隐藏在 O(log n) 里。

k 或 arr[i] 很大时怎么防溢出？

使用语言提供的安全整数类型或 64 位整数，检查 k + left 和 arr[i] - i - 1 的范围。若业务允许任意大整数，接口和测试应明确 BigInt 或等价表示。

评分标准

能从计数公式推导单调谓词、给出半开区间实现并解释答案公式，可评为强通过；若只会背代码、无法证明边界，应继续追问。