基于排序数组中“第K个缺失的正整数”的二分查找解法
字数 3022 2025-12-23 23:17:55

基于排序数组中“第K个缺失的正整数”的二分查找解法

题目描述
给定一个严格递增的整数数组 arr 和整数 k，你需要找到并返回缺失的正整数序列中第 k 个缺失的正整数。

  • 缺失的正整数定义为：不在数组 arr 中，并且是正整数（从 1 开始）的那些数。
  • 例如，arr = [2,3,4,7,11], k = 5，缺失的正整数序列是 [1,5,6,8,9,10,12,...]，第 5 个是 9。

解题过程循序渐进讲解
我们先从一个直观思路开始，逐步优化到高效算法。

1. 基础思路：模拟查找
最简单的想法是从 1 开始逐个正整数检查是否在数组中，若不在则计数，直到找到第 k 个缺失的数。

  • 用指针 i 遍历数组，用 currentNum 从 1 开始递增。
  • 如果 currentNum 等于 arr[i]，说明这个数存在，i 前进；否则说明 currentNum 缺失，缺失计数加一。
  • 当缺失计数等于 k 时，当前 currentNum 就是答案。
    这个方法的时间复杂度是 O(n + m)，其中 m 是答案的值，在最坏情况下（数组元素很大，k 很大）可能接近 O(n + k)，效率较低。

2. 核心观察：利用“到当前位置为止缺失的数量”
对于数组的某个位置 i（索引从 0 开始），arr[i] 这个值本身表示正整数序列中第 arr[i] 个数。

  • 在 arr[i] 之前（包括自身），本应有的正整数总数是 arr[i] 个。
  • 但实际上数组到 i 位置为止只有 i+1 个数存在。
  • 所以，到 arr[i] 为止，缺失的正整数的数量是：
    missingCount = arr[i] - (i+1)
    解释：arr[i] 是当前应到的正整数，i+1 是实际存在的数量，差值即为缺失数数量。

3. 例子验证公式
数组 arr = [2,3,4,7,11]：

  • i=0, arr[0]=2, missingCount = 2 - (0+1) = 1（缺失了 1）。
  • i=1, arr[1]=3, missingCount = 3 - 2 = 1（缺失了 1）。
  • i=2, arr[2]=4, missingCount = 4 - 3 = 1（缺失了 1）。
  • i=3, arr[3]=7, missingCount = 7 - 4 = 3（缺失了 1,5,6）。
  • i=4, arr[4]=11, missingCount = 11 - 5 = 6（缺失了 1,5,6,8,9,10）。

4. 二分查找的引入
由于数组严格递增，missingCount 随 i 单调不减。
我们要找的是第 k 个缺失的正整数，也就是找到最小的索引 i，使得到 arr[i] 为止缺失的数量 ≥ k。
因为缺失数是连续的，如果我们找到第一个缺失数 ≥ k 的位置 i，那么：

  • 如果 i=0，意味着在第一个数组元素之前就有足够缺失，答案 = k。
  • 否则，答案 = arr[i-1] + (k - missingCountAt(i-1))，其中 missingCountAt(i-1) 是到 arr[i-1] 为止的缺失数。
    更简单的方法：直接在 0 到 n-1 的索引范围内进行二分查找，找第一个满足 arr[mid] - (mid+1) >= k 的 mid。

5. 二分查找步骤

  • 初始化 left=0, right=n-1。
  • 当 left ≤ right 时：
    • mid = (left+right)/2。
    • 计算 missing = arr[mid] - mid - 1。
    • 如果 missing < k，说明到 mid 为止缺失数还不够 k，答案在右侧：left = mid+1。
    • 否则 missing ≥ k，说明到 mid 为止缺失数已经达到或超过 k，记录可能的 mid，并继续在左侧找更小的：right = mid-1。
  • 循环结束后，left 是第一个满足 missing ≥ k 的索引（如果 left 超出数组范围，说明所有数之前缺失还不够 k）。
  • 如果 left == 0，说明在第一个元素之前就缺失了 k 个，那么答案 = k。
  • 否则，计算到 left-1 为止缺失了多少：missingBefore = arr[left-1] - (left-1) - 1。
  • 答案 = arr[left-1] + (k - missingBefore)。

6. 实例推演
arr = [2,3,4,7,11], k=5。

  • left=0, right=4, mid=2, missing=4-2-1=1<5 → left=3。
  • left=3, right=4, mid=3, missing=7-3-1=3<5 → left=4。
  • left=4, right=4, mid=4, missing=11-4-1=6≥5 → right=3。
    循环结束，left=4。
    因为 left>0，计算 missingBefore = arr[3] - 3 - 1 = 7-4=3。
    答案 = arr[3] + (5-3) = 7+2 = 9。
    符合预期。

7. 边界情况处理

  • 如果 k 很大，超过数组最大元素能提供的缺失数，比如 arr=[1,2,3], k=5，则 left 最终会变成 n（数组长度），此时可以直接返回 arr[n-1] + (k - missingAt(n-1))，即最后一个元素之后继续数缺失数。
  • 代码实现时，可以让 right 初始为 n（而不是 n-1），这样二分查找范围包含“最后一个元素之后”的位置，最后统一公式：
    • 如果 left == 0，答案为 k。
    • 否则，答案为 arr[left-1] + (k - (arr[left-1] - (left-1) - 1))，简化后为：
      arr[left-1] + k - (arr[left-1] - left) = left + k。
      惊喜的简化结果：答案 = left + k。
      验证：上例 left=4, k=5 → 4+5=9。
      另一个例子：arr=[1,2,3], k=5, 二分后 left=3, 3+5=8 正好是第 5 个缺失数（缺失序列 4,5,6,7,8,...）。

8. 最终算法步骤

  1. 初始化 left=0, right=n。
  2. 当 left < right:
    • mid = (left+right)/2。
    • missing = arr[mid] - mid - 1。
    • 如果 missing < k: left = mid+1。
    • 否则: right = mid。
  3. 二分结束后，left 就是满足条件的第一个位置。
  4. 返回 left + k。

9. 复杂度分析
时间复杂度 O(log n)，因为只需要一次二分查找。
空间复杂度 O(1)。

10. 思考延伸
这个技巧本质上是在缺失数量的单调性上做二分查找，将“找第 k 个缺失数”转化为“找第一个缺失数 ≥ k 的位置”，然后利用索引和值的直接计算得到结果，避免了逐个枚举。这种思路在类似“有序数组中缺失元素”问题中很常见。

基于排序数组中“第K个缺失的正整数”的二分查找解法 题目描述 给定一个严格递增的整数数组 arr 和整数 k ，你需要找到并返回 缺失的正整数序列中第 k 个 缺失的正整数。 缺失的正整数定义为：不在数组 arr 中，并且是正整数（从 1 开始）的那些数。 例如， arr = [2,3,4,7,11] , k = 5 ，缺失的正整数序列是 [ 1,5,6,8,9,10,12,... ]，第 5 个是 9。 解题过程循序渐进讲解 我们先从一个直观思路开始，逐步优化到高效算法。 1. 基础思路：模拟查找 最简单的想法是从 1 开始逐个正整数检查是否在数组中，若不在则计数，直到找到第 k 个缺失的数。 用指针 i 遍历数组，用 currentNum 从 1 开始递增。 如果 currentNum 等于 arr[i] ，说明这个数存在， i 前进；否则说明 currentNum 缺失，缺失计数加一。 当缺失计数等于 k 时，当前 currentNum 就是答案。 这个方法的时间复杂度是 O(n + m)，其中 m 是答案的值，在最坏情况下（数组元素很大，k 很大）可能接近 O(n + k)，效率较低。 2. 核心观察：利用“到当前位置为止缺失的数量” 对于数组的某个位置 i （索引从 0 开始）， arr[i] 这个值本身表示正整数序列中第 arr[i] 个数。 在 arr[i] 之前（包括自身），本应有的正整数总数是 arr[i] 个。 但实际上数组到 i 位置为止只有 i+1 个数存在。 所以，到 arr[i] 为止，缺失的正整数的数量是： missingCount = arr[i] - (i+1) 解释： arr[i] 是当前应到的正整数， i+1 是实际存在的数量，差值即为缺失数数量。 3. 例子验证公式 数组 arr = [2,3,4,7,11] ： i=0, arr[ 0 ]=2, missingCount = 2 - (0+1) = 1（缺失了 1）。 i=1, arr[ 1 ]=3, missingCount = 3 - 2 = 1（缺失了 1）。 i=2, arr[ 2 ]=4, missingCount = 4 - 3 = 1（缺失了 1）。 i=3, arr[ 3 ]=7, missingCount = 7 - 4 = 3（缺失了 1,5,6）。 i=4, arr[ 4 ]=11, missingCount = 11 - 5 = 6（缺失了 1,5,6,8,9,10）。 4. 二分查找的引入 由于数组严格递增， missingCount 随 i 单调不减。 我们要找的是 第 k 个缺失的正整数 ，也就是找到最小的索引 i，使得到 arr[ i ] 为止缺失的数量 ≥ k。 因为缺失数是连续的，如果我们找到第一个缺失数 ≥ k 的位置 i，那么： 如果 i=0，意味着在第一个数组元素之前就有足够缺失，答案 = k。 否则，答案 = arr[ i-1] + (k - missingCountAt(i-1))，其中 missingCountAt(i-1) 是到 arr[ i-1 ] 为止的缺失数。 更简单的方法：直接在 0 到 n-1 的索引范围内进行二分查找，找第一个满足 arr[mid] - (mid+1) >= k 的 mid。 5. 二分查找步骤 初始化 left=0, right=n-1。 当 left ≤ right 时： mid = (left+right)/2。 计算 missing = arr[ mid ] - mid - 1。 如果 missing < k，说明到 mid 为止缺失数还不够 k，答案在右侧：left = mid+1。 否则 missing ≥ k，说明到 mid 为止缺失数已经达到或超过 k，记录可能的 mid，并继续在左侧找更小的：right = mid-1。 循环结束后，left 是第一个满足 missing ≥ k 的索引（如果 left 超出数组范围，说明所有数之前缺失还不够 k）。 如果 left == 0，说明在第一个元素之前就缺失了 k 个，那么答案 = k。 否则，计算到 left-1 为止缺失了多少：missingBefore = arr[ left-1 ] - (left-1) - 1。 答案 = arr[ left-1 ] + (k - missingBefore)。 6. 实例推演 arr = [ 2,3,4,7,11 ], k=5。 left=0, right=4, mid=2, missing=4-2-1=1 <5 → left=3。 left=3, right=4, mid=3, missing=7-3-1=3 <5 → left=4。 left=4, right=4, mid=4, missing=11-4-1=6≥5 → right=3。 循环结束，left=4。 因为 left>0，计算 missingBefore = arr[ 3 ] - 3 - 1 = 7-4=3。 答案 = arr[ 3 ] + (5-3) = 7+2 = 9。 符合预期。 7. 边界情况处理 如果 k 很大，超过数组最大元素能提供的缺失数，比如 arr=[ 1,2,3], k=5，则 left 最终会变成 n（数组长度），此时可以直接返回 arr[ n-1 ] + (k - missingAt(n-1))，即最后一个元素之后继续数缺失数。 代码实现时，可以让 right 初始为 n（而不是 n-1），这样二分查找范围包含“最后一个元素之后”的位置，最后统一公式： 如果 left == 0，答案为 k。 否则，答案为 arr[ left-1] + (k - (arr[ left-1 ] - (left-1) - 1))，简化后为： arr[left-1] + k - (arr[left-1] - left) = left + k 。 惊喜的简化结果：答案 = left + k。 验证：上例 left=4, k=5 → 4+5=9。 另一个例子：arr=[ 1,2,3 ], k=5, 二分后 left=3, 3+5=8 正好是第 5 个缺失数（缺失序列 4,5,6,7,8,...）。 8. 最终算法步骤 初始化 left=0, right=n。 当 left < right: mid = (left+right)/2。 missing = arr[ mid ] - mid - 1。 如果 missing < k: left = mid+1。 否则: right = mid。 二分结束后，left 就是满足条件的第一个位置。 返回 left + k。 9. 复杂度分析 时间复杂度 O(log n)，因为只需要一次二分查找。 空间复杂度 O(1)。 10. 思考延伸 这个技巧本质上是 在缺失数量的单调性上做二分查找 ，将“找第 k 个缺失数”转化为“找第一个缺失数 ≥ k 的位置”，然后利用索引和值的直接计算得到结果，避免了逐个枚举。这种思路在类似“有序数组中缺失元素”问题中很常见。