LeetCode-Go 题解：1539. Kth Missing Positive Number —— 寻找第 k 个缺失正整数的双指针解法
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
导读
本题是 LeetCode 第 1539 题Kth Missing Positive Number（第 k 个缺失的正整数），要求在一个严格递增的正整数数组中，找出缺失的第k个正整数。本仓库以 LeetCode-Go 项目为载体，给出了一个时间、空间均为O(1)额外空间的线性双指针解法。读完本文，你将掌握该题的完整题意、两种边界情况（缺失值在数组内部 / 数组之后）、Go 实现细节，以及仓库内配套的单元测试如何验证正确性。
题目描述
给定一个严格递增的正整数数组arr和一个整数k，返回数组中缺失的第k个正整数。
- 数组元素均为正整数，且严格递增，即
arr[i] < arr[j]（1 <= i < j <= arr.length）； - 缺失的正整数是指不在数组中出现的正整数，从 1 开始计数。
示例 1
Input: arr = [2,3,4,7,11], k = 5 Output: 9解释：正整数序列1,2,3,4,5,6,7,8,9,10,...中，数组中缺失的是[1,5,6,8,9,10,12,13,...]，第 5 个缺失值为9。
示例 2
Input: arr = [1,2,3,4], k = 2 Output: 6解释：数组中缺失的是[5,6,7,...]，第 2 个缺失值为6。该示例对应题目说明中的特殊情况：所有缺失值都位于数组元素之外（即大于数组末尾）。
数据约束
1 <= arr.length <= 10001 <= arr[i] <= 10001 <= k <= 1000arr[i] < arr[j]，数组严格递增，不存在重复元素
题目大意
给你一个严格升序排列的正整数数组arr和一个整数k，请找到这个数组里第k个缺失的正整数。
解题思路
本题属于简单题（Easy），核心思想是用正整数计数器与数组下标双指针同步前进，缺一个数就消耗一次k。具体做法如下：
- 用一个变量
positive从 1 开始递增，模拟"当前正在检查的正整数"； - 用一个下标
index指向数组当前元素； - 每轮循环比较
arr[index]与positive：- 若
arr[index] != positive，说明positive这个正整数缺失，令k--； - 若相等，说明数组中包含
positive，index++继续向后比较；
- 若
- 每轮结束时判断
k是否为 0：- 若
k == 0，说明已经找到第 k 个缺失值，直接返回positive； - 否则
positive++，继续下一轮；
- 若
- 循环退出后若
k仍不为 0（对应示例 2 的边界情况，即缺失值全部位于数组末尾之后），此时第 k 个缺失值应为positive + k - 1，因为positive是当前最后一个未匹配到的整数，其后的k-1个正整数也都是缺失的。
时间复杂度与空间复杂度
- 时间复杂度：
O(n)，其中n = len(arr)，最坏情况下需要遍历整个数组； - 空间复杂度：
O(1)，仅使用两个整型变量，没有额外数据结构。
参考代码（Go）
仓库中该题的完整实现位于 leetcode/1539.Kth-Missing-Positive-Number：
package leetcode func findKthPositive(arr []int, k int) int { positive, index := 1, 0 for index < len(arr) { if arr[index] != positive { k-- } else { index++ } if k == 0 { break } positive++ } if k != 0 { positive += k - 1 } return positive }代码逐步拆解
- 第 4 行：初始化
positive = 1（从最小的正整数开始检查）、index = 0（数组游标）； - 第 5～15 行：主循环，仅当下标未越界时执行；
- 第 6～10 行：
arr[index]与positive不相等说明positive缺失，k--；相等则index++； - 第 11～14 行：
k减到 0 立即break，避免多余的循环； - 第 16～19 行：循环结束后若
k仍大于 0，说明缺失值都集中在数组之后，直接算术收尾：positive += k - 1。
边界情况推演
| 场景 | 输入 | 推导过程 | 输出 |
|---|---|---|---|
| 缺失值在数组内部 | arr=[2,3,4,7,11], k=5 | 1 缺失(k=4)、5 缺失(k=3)、6 缺失(k=2)、8 缺失(k=1)、9 缺失(k=0) | 9 |
| 缺失值在数组之后 | arr=[1,2,3,4], k=2 | 数组遍历完 k 仍为 2，positive=5，5 + 2 - 1 = 6 | 6 |
单元测试与验证
仓库为每个题目目录都配套了_test.go测试文件，本题的测试见 leetcode/1539.Kth-Missing-Positive-Number/1539. Kth Missing Positive Number_test.go。测试使用标准库testing编写，覆盖了题目给出的两个官方示例：
func Test_Problem1539(t *testing.T) { qs := []question1539{ { para1539{[]int{2, 3, 4, 7, 11}, 5}, ans1539{9}, }, { para1539{[]int{1, 2, 3, 4}, 2}, ans1539{6}, }, } // ... for _, q := range qs { _, p := q.ans1539, q.para1539 fmt.Printf("【input】:%v 【output】:%v \n", p, findKthPositive(p.arr, p.k)) } }- 测试数据通过
para1539（入参arr、k）与ans1539（期望输出）两个结构体组织成表驱动用例； - 覆盖了"缺失值在数组内部"与"缺失值在数组末尾之后"两种典型分支，与算法实现中的两个关键路径一一对应；
- 运行方式：进入仓库根目录后执行
go test ./leetcode/1539.Kth-Missing-Positive-Number/ -run Test_Problem1539 -v（需本地安装 Go，仓库go.mod声明go 1.19）。
此外，项目根目录的 gotest.sh 提供了一次性覆盖整个leetcode/包目录的测试入口（go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...），可用于将本题纳入全量回归。
从题解反推的思路扩展
本题是"有序数组 + 缺失计数"类问题的入门模板，理解其双指针思想后，可以自然迁移到以下同类问题：
- 268. Missing Number：无序数组中找出唯一缺失的一个数，可用异或或求和公式；
- 41. First Missing Positive：找出缺失的最小正整数，需要借助"值域与下标映射"进行原地标记；
- 1060. Missing Element in Sorted Array（会员题）：在有序数组中找第 k 个缺失元素，是本题的进阶版，可用二分查找优化到
O(log n)。
本题由于约束中arr[i] <= 1000、k <= 1000，数据规模很小，线性扫描已足够；若数据规模扩大，可进一步推导数学公式：对于下标i，arr[i] - (i+1)表示扫描到arr[i]时累计缺失的数量，据此可二分定位第 k 个缺失值的位置，这也是从简单题通往二分思想的自然延伸。
小结
本题通过"正整数计数器 + 数组下标"两个指针同步扫描，在O(n)时间内、O(1)额外空间下求解第 k 个缺失正整数；代码实现短小精悍，配合 1539.Kth-Missing-Positive-Number 目录下的源码与表驱动测试，可直接运行验证。掌握这道题，也就掌握了有序数组缺失计数类问题的基础范式。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
