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 开始计数。示例 1Input: 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。示例 2Input: 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--若相等说明数组中包含positiveindex继续向后比较每轮结束时判断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-Numberpackage 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数组游标第 515 行主循环仅当下标未越界时执行第 610 行arr[index]与positive不相等说明positive缺失k--相等则index第 1114 行k减到 0 立即break避免多余的循环第 1619 行循环结束后若k仍大于 0说明缺失值都集中在数组之后直接算术收尾positive k - 1。边界情况推演场景输入推导过程输出缺失值在数组内部arr[2,3,4,7,11], k51 缺失(k4)、5 缺失(k3)、6 缺失(k2)、8 缺失(k1)、9 缺失(k0)9缺失值在数组之后arr[1,2,3,4], k2数组遍历完 k 仍为 2positive55 2 - 1 66单元测试与验证仓库为每个题目目录都配套了_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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...可用于将本题纳入全量回归。从题解反推的思路扩展本题是有序数组 缺失计数类问题的入门模板理解其双指针思想后可以自然迁移到以下同类问题268. Missing Number无序数组中找出唯一缺失的一个数可用异或或求和公式41. First Missing Positive找出缺失的最小正整数需要借助值域与下标映射进行原地标记1060. Missing Element in Sorted Array会员题在有序数组中找第 k 个缺失元素是本题的进阶版可用二分查找优化到O(log n)。本题由于约束中arr[i] 1000、k 1000数据规模很小线性扫描已足够若数据规模扩大可进一步推导数学公式对于下标iarr[i] - (i1)表示扫描到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），仅供参考