LeetCode-Go 题解 719：Find K-th Smallest Pair Distance 二分答案 + 双指针计数

LeetCode-Go 题解 719Find K-th Smallest Pair Distance 二分答案 双指针计数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本题来自 LeetCode 第 719 题「Find K-th Smallest Pair Distance」Hard要求在一个整数数组中找出所有数对距离绝对差中第 k 小的那一个。本仓库 LeetCode-Go 以 Go 实现了该题的标准解法先排序再对距离值域做二分搜索配合双指针在 O(n) 内统计小于等于某个阈值的数对个数。读完本文你将掌握第 k 小问题转二分判定的通用套路以及如何在排序数组上用双指针高效统计差值对数量并能直接对照仓库内的完整源码与测试用例进行验证。题目定义给定一个整数数组nums返回所有数对之间第 k 小的距离。数对(A, B)的距离定义为A与B的绝对差值。示例 1Input: nums [1,3,1] k 1 Output: 0解释数组的所有数对及其距离为(1,3) - 2(1,1) - 0(3,1) - 2排序后距离序列为[0, 2, 2]第 1 小的距离是(1,1)对应的0。题目约束Note2 len(nums) 100000 nums[i] 10000001 k len(nums) * (len(nums) - 1) / 2第三个约束说明 k 的取值范围覆盖了全部n*(n-1)/2个数对含重复组合因此答案必然存在。注意两两元素之差可能重复重复的差值要按多个计数不去重这一点直接决定了计数函数的写法。解题思路二分答案 判定函数为什么不能直接枚举n最大可达 10000数对总数为n*(n-1)/2 ≈ 5×10^7。若把所有差值全部枚举出来再排序取第 k 小空间和时间都无法承受。因此需要换一个角度不直接求第 k 小的距离而是猜测一个距离mid然后判定距离 ≤ mid 的数对有多少个——这就是经典的二分答案 判定Binary Search on Answer模式。二分区间如何确定先将原数组排序排序不改变数对绝对差的值则最小可能距离是0相同元素或相邻元素相减最大可能距离是nums[len(nums)-1] - nums[0]首尾之差。于是答案在闭区间[0, nums[len(nums)-1] - nums[0]]内搜索。每次取mid统计距离不超过mid的数对个数cnt(mid)若cnt(mid) k说明第 k 小的距离 ≤mid收缩右边界high mid否则说明第 k 小的距离 mid提升左边界low mid 1。当low high时即为答案。cnt(mid)关于mid单调不减这正是二分可用的前提。核心难点因此转化为如何在有序数组上高效计算满足nums[j] - nums[i] ≤ mid的数对总数。源码实现主函数与两种计数法仓库完整实现位于 719. Find K-th Smallest Pair Distance.go全文约 45 行包含主函数与两种计数实现。主函数二分框架func smallestDistancePair(nums []int, k int) int { sort.Ints(nums) low, high : 0, nums[len(nums)-1]-nums[0] for low high { mid : low (high-low)1 tmp : findDistanceCount(nums, mid) if tmp k { high mid } else { low mid 1 } } return low }实现要点先sort.Ints(nums)排序为后续双指针计数打基础二分区间初始化为[0, 最大值差]mid : low (high-low)1用移位代替除法且可避免(lowhigh)溢出判定条件采用tmp k时收缩右边界这是找第 k 小的标准写法保证最终落在第一个满足cnt(答案) k的距离上即恰为第 k 小的距离。解法一本题正解双指针计数// 解法一 双指针 func findDistanceCount(nums []int, num int) int { count, i : 0, 0 for j : 1; j len(nums); j { for nums[j]-nums[i] num i j { i } count (j - i) } return count }原理详解数组有序后固定右指针j需要统计所有满足nums[j] - nums[i] num的左端点i的个数。由于数组单调不减当j增大时满足条件的i的起始位置只会单调右移nums[j]变大若仍要差值不超过numi只能往右移动因此可以用一个滑动窗口内层for循环把i向右推进直到nums[j]-nums[i] num或i j此时下标区间[i, j-1]内任意一个元素作为左端点与nums[j]组成的数对距离都不超过num共有j - i个累加进count。i全程最多移动 n 次j移动 n 次所以单次计数复杂度为O(n)。整个算法是sort O(n log n) 二分O(log(maxDiff) × n)。解法二暴力计数参照/校验用// 解法二 暴力查找 func findDistanceCount1(nums []int, num int) int { count : 0 for i : 0; i len(nums); i { for j : i 1; j len(nums); j { if nums[j]-nums[i] num { count } } } return count }这是最容易理解的两重循环写法直接枚举所有(i, j)组合并判断nums[j]-nums[i] num时间复杂度O(n²)。虽然正确但在n 10000时约 5×10^7 次判断且该计数在二分过程中会被调用约 20 次log(maxDiff) ≈ log(10^6) ≈ 20总开销约 10^9 级别无法通过。仓库中保留它主要用于正确性对照测试用例里专门断言了双指针计数与暴力计数的结果一致详见下文测试章节。正确性验证测试用例解析对应测试文件为 719. Find K-th Smallest Pair Distance_test.go包含 5 组用例覆盖了多种边界与一般情形输入numsk期望输出[1, 3, 1]10[1, 1, 1]20[1, 6, 1]35[62, 100, 4]258[9, 10, 7, 10, 6, 1, 5, 4, 9, 8]182用例亮点[1, 1, 1]验证全等元素时所有距离均为 0 的退化情形[1, 6, 1]排序后[1, 1, 6]验证重复元素与中等差值混合的排序场景最后一个 10 元素用例验证较大规模输入下算法的正确性。测试代码在每次调用后还执行了双指针计数与暴力计数的交叉校验测试文件if c1, c2 : findDistanceCount(p.num, a.one), findDistanceCount1(p.num, a.one); c1 ! c2 { t.Fatalf(distance count mismatch for %v, num%v: %v vs %v, p.num, a.one, c1, c2) }这保证了 O(n) 双指针计数与朴素枚举在已排序数组上对同一距离阈值的计数结果严格一致从测试层面佐证了滑动窗口实现的正确性。仓库根目录的 coverage.txt 显示该文件所有函数块主函数与两种计数函数均被测试覆盖到符合本仓库100% test coverage的工程约定仓库的 gotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性对全部题解包做覆盖率统计说明所有 leetcode 子目录题目均以同一套测试流程保障。本地运行测试在仓库根目录执行go test ./leetcode/0719.Find-K-th-Smallest-Pair-Distance/...即可单独运行本题测试或执行仓库根目录的./gotest.sh运行全部题解测试并生成覆盖率文件。测试通过时会输出------------------------Leetcode Problem 719------------------------ 【input】:[1 3 1] 【output】:0 ...复杂度与正确性小结环节复杂度排序O(n log n)二分次数O(log(max(nums)-min(nums))) ≈ O(log 10^6) ≈ 20 次单次双指针计数O(n)总体时间O(n log n n log(maxDiff))空间O(1)排序为原地计数仅用常量变量正确性由二分区间单调性 计数函数精确性双重保证cnt(mid)随mid单调不减因此第一个满足cnt(mid) k的mid正是第 k 小的距离双指针计数在有序数组上精确统计了所有nums[j]-nums[i] mid的组合且经暴力法逐用例交叉验证。延伸同一套路的相关题目二分答案 判定以及有序数据中找第 k 小元素是本仓库中反复出现的题型与本题同属一个系列的还包括373. Find K Pairs with Smallest Sums两个有序数组中找和最小的 k 个数对378. Kth Smallest Element in a Sorted Matrix有序矩阵中找第 k 小元素668. Kth Smallest Number in Multiplication Table乘法表中找第 k 小数字786. K-th Smallest Prime Fraction素数分数数组中找第 k 小分数。这组题目共同的思维模型是当直接构造并排序所有候选不可行时转而对答案值域二分把求第 k 小转化为统计 ≤ mid 的个数这一可高效计算的判定问题。本题的双指针计数正是这一模型在有序数组差值对上的具体落地掌握它即可举一反三应对上述系列题。参考文件索引题解说明文档README.mdGo 完整实现双指针 暴力计数719. Find K-th Smallest Pair Distance.go测试用例与双指针/暴力交叉校验719. Find K-th Smallest Pair Distance_test.go覆盖率证据coverage.txt全仓测试脚本gotest.sh【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考