LeetCode-Go 题解786. K-th Smallest Prime Fraction第 K 个最小的素数分数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于开源仓库 LeetCode-Go 中 leetcode/0786.K-th-Smallest-Prime-Fraction/README.md 及对应 Go 源码完整讲解 LeetCode 第 786 题「第 K 个最小的素数分数」的两种解法暴力枚举排序与实数域二分搜索。读完本文你将掌握如何将「求第 K 小的分数」转化为「按值域二分 单调计数」的通用模型并理解 LeetCode-Go 仓库中同系列题目373、378、668、719、786的共性套路。题目描述一个已排序的列表A包含1以及若干素数。对于列表中任意满足p q的一对元素都可以构造一个分数p/q。请问所有可构造分数中第K小的分数是多少以整数数组的形式返回答案其中answer[0] panswer[1] q。示例 1Input: A [1, 2, 3, 5], K 3 Output: [2, 5]解释按升序排列的所有分数为1/5, 1/3, 2/5, 1/2, 3/5, 2/3第 3 个分数是2/5。示例 2Input: A [1, 7], K 1 Output: [1, 7]数据范围NoteA的长度在2到2000之间每个A[i]的值在1到30000之间K的取值范围是1到A.length * (A.length - 1) / 2即所有真分数的总数。这意味着最坏情况下分数数量约为2000 * 1999 / 2 ≈ 200 万暴力解法虽然可行但二分搜索才是符合大型输入规模的更优方案。解题思路总览原文档给出的核心思路可以归纳为两条主线暴力解法枚举所有可能的真分数(p, q)排序后直接输出第K小。注意排序时不能直接用浮点数比较必须转化为分子、分母的结构体用交叉相乘的方式比较大小避免浮点精度问题。最优解法二分搜索由于所有真分数都小于 1二分搜索范围是[0, 1]。每次取中点mid统计值小于mid的分数个数count并动态维护小于mid的分数中最大的那一个记录其分子与分母。根据count与K的大小关系收缩区间直到恰好找到第K小的分数。解法一暴力枚举 结构体排序O(n²)核心思想用两层循环枚举所有i j的组合(A[i], A[j])把每一对作为分子、分母存入结构体切片然后整体排序取第K - 1个元素即可。源码实现见仓库文件 leetcode/0786.K-th-Smallest-Prime-Fraction/786. K-th Smallest Prime Fraction.go核心代码如下// 解法二 暴力解法时间复杂度 O(n^2) func kthSmallestPrimeFraction1(A []int, K int) []int { if len(A) 0 || (len(A)*(len(A)-1))/2 K { return []int{} } fractions : []Fraction{} for i : 0; i len(A); i { for j : i 1; j len(A); j { fractions append(fractions, Fraction{molecule: A[i], denominator: A[j]}) } } sort.Sort(SortByFraction(fractions)) return []int{fractions[K-1].molecule, fractions[K-1].denominator} } // Fraction define type Fraction struct { molecule int denominator int } // SortByFraction define type SortByFraction []Fraction func (a SortByFraction) Len() int { return len(a) } func (a SortByFraction) Swap(i, j int) { a[i], a[j] a[j], a[i] } func (a SortByFraction) Less(i, j int) bool { return a[i].molecule*a[j].denominator a[j].molecule*a[i].denominator }关键细节为什么不能用 float 排序如果直接计算float64(p)/float64(q)再排序在数据量大、分数值非常接近时可能因浮点精度产生错误顺序。而SortByFraction.Less采用交叉相乘a[i].molecule * a[j].denominator a[j].molecule * a[i].denominator等价于比较a[i].molecule / a[i].denominator a[j].molecule / a[j].denominator全程使用整数运算杜绝精度误差。这正是原文档强调排序的时候不能直接用 float 排序需要转化成分子和分母的结构体进行排序的原因。边界处理源码在入口处做了两个防御判断输入数组为空len(A) 0K超过所有真分数的总数(len(A)*(len(A)-1))/2 K。此时直接返回空切片[]int{}对应测试用例 786. K-th Smallest Prime Fraction_test.go 中的边界分支验证// 覆盖暴力解法的边界分支空输入或 K 超过分数总数时返回空切片 if got : kthSmallestPrimeFraction1([]int{}, 1); len(got) ! 0 { t.Fatalf(kthSmallestPrimeFraction1([], 1) %v, want [], got) } if got : kthSmallestPrimeFraction1([]int{1, 2}, 5); len(got) ! 0 { t.Fatalf(kthSmallestPrimeFraction1([1 2], 5) %v, want [], got) }时间复杂度为O(n² log n)枚举O(n²)个分数 排序O(n² log n²)空间复杂度为O(n²)。解法二实数域二分搜索最优解核心思想因为所有真分数p/qp q都落在(0, 1)区间内所以可以在实数域[0, 1]上进行二分。对每个中点mid需要回答两个问题值严格小于mid的分数有多少个记为count这些小于mid的分数中最大的一个是谁记录其分子p、分母q。如果count K说明第K小的分数恰好就是当前维护的最大分数直接返回如果count K说明答案在更大的区间令low mid否则令high mid。源码实现// 解法一 二分搜索 func kthSmallestPrimeFraction(A []int, K int) []int { low, high, n : 0.0, 1.0, len(A) // 因为是在小数内使用二分查找无法像在整数范围内那样通过 mid1 和边界判断来终止循环 // 所以此处根据 count 来结束循环 for { mid, count, p, q, j : (highlow)/2.0, 0, 0, 1, 0 for i : 0; i n; i { for j n float64(A[i]) float64(mid)*float64(A[j]) { j } count n - j if j n q*A[i] p*A[j] { p A[i] q A[j] } } if count K { return []int{p, q} } else if count K { low mid } else { high mid } } }逐行拆解第 9 行二分区间初始化为[0.0, 1.0]n为数组长度。第 12 行由于是在实数域二分无法像整数二分那样通过mid1与边界判断终止循环因此以count是否恰好等于K作为循环出口注释中已明确说明这一点。第 13 行mid为区间中点count统计小于mid的分数个数p、q记录小于mid的最大分数的分子、分母初始为0/1j是指向分母的游标。第 14–23 行对每个分子A[i]利用数组有序性维护单调指针j只要A[i] mid * A[j]就右移j。此时A[i]/A[j] mid到A[i]/A[n-1]之间的分数都大于等于mid因此小于mid的分数个数为n - j累加到count。同时用交叉相乘q*A[i] p*A[j]判断并更新小于mid的最大分数。第 24–30 行count K直接返回count K说明第 K 小的分数比mid大缩小区间左边界否则缩小右边界。为什么用q*A[i] p*A[j]而不是浮点除法维护最大分数时同样采用整数交叉相乘A[i] / A[j] p / q等价于q * A[i] p * A[j]避免浮点误差保证最终返回的分子分母一定是数组中的精确元素。复杂度分析外层二分在实数域上进行收敛轮数与精度相关由于分数是有限个且来自有限数组实际只需迭代到某个count K的精确值即终止每次count统计中j指针单调递增单次统计为O(n)空间复杂度O(1)仅使用常数个变量。相比暴力解法的O(n²)空间二分搜索在空间上具有压倒性优势且时间上通常远快于枚举全部分数并排序。测试用例验证仓库测试文件 786. K-th Smallest Prime Fraction_test.go 覆盖了以下用例输入AK期望输出[1, 2, 3, 5]3[2, 5]对应题面示例[1, 7]1[1, 7]对应题面示例[1, 2]1[1, 2]最小规模[1, 2, 3, 5, 7]6[3, 7]测试同时调用两种解法并互相校验got : kthSmallestPrimeFraction1(p.A, p.K) if got[0] ! a.one[0] || got[1] ! a.one[1] { t.Fatalf(kthSmallestPrimeFraction1(%v, %d) %v, want %v, p.A, p.K, got, a.one) }注意此处二分解法直接作为输出打印暴力解法结果与期望答案比对外加对空输入与K越界两个边界分支的断言保证了暴力解法的健壮性。你可以按仓库统一的测试脚本运行验证go test ./leetcode/0786.K-th-Smallest-Prime-Fraction/... -v仓库根目录的 gotest.sh 展示了整个项目采用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...的方式进行全量覆盖率测试题解均要求 100% 测试覆盖。同系列题目已排序矩阵/序列中求第 K 小元素原文档明确指出这类在已排序的结构中寻找第 K 小元素的题目在仓库中有一个系列第 373 题Find K Pairs with Smallest Sums —— 从两个升序数组中找和最小的 K 个数对第 378 题Kth Smallest Element in a Sorted Matrix —— 在行列均升序的矩阵中找第 K 小元素仓库源码 378. Kth Smallest Element in a Sorted Matrix.go 同样提供了二分与堆两种实现第 668 题Kth Smallest Number in Multiplication Table —— 在乘法表中找第 K 小数字第 719 题Find K-th Smallest Pair Distance —— 在数组元素对的绝对差中找第 K 小距离第 786 题本题在素数真分数中找第 K 小分数。这类问题的通用套路是用单调计数函数回答小于等于/小于 x 的元素有多少个再配合值域二分逼近答案。786 题的独特点在于答案是一个分数需要额外维护小于 mid 的最大分数的分子分母这也是区分度最高的地方。小结维度暴力解法二分搜索解法时间复杂度O(n² log n)每轮O(n)轮数与值域收敛相关空间复杂度O(n²)O(1)精度风险需结构体交叉相乘规避全程整数交叉相乘无浮点比较适用规模小规模输入大规模输入n最大 2000实战建议作为题解理解暴力解法直观易写适合快速验证答案作为生产级实现优先采用二分搜索解法其在空间与时间上均显著更优。结合 README.md、题解源码 与 测试文件 三者对照阅读即可完整掌握本题的所有细节。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解：786. K-th Smallest Prime Fraction（第 K 个最小的素数分数）
LeetCode-Go 题解786. K-th Smallest Prime Fraction第 K 个最小的素数分数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于开源仓库 LeetCode-Go 中 leetcode/0786.K-th-Smallest-Prime-Fraction/README.md 及对应 Go 源码完整讲解 LeetCode 第 786 题「第 K 个最小的素数分数」的两种解法暴力枚举排序与实数域二分搜索。读完本文你将掌握如何将「求第 K 小的分数」转化为「按值域二分 单调计数」的通用模型并理解 LeetCode-Go 仓库中同系列题目373、378、668、719、786的共性套路。题目描述一个已排序的列表A包含1以及若干素数。对于列表中任意满足p q的一对元素都可以构造一个分数p/q。请问所有可构造分数中第K小的分数是多少以整数数组的形式返回答案其中answer[0] panswer[1] q。示例 1Input: A [1, 2, 3, 5], K 3 Output: [2, 5]解释按升序排列的所有分数为1/5, 1/3, 2/5, 1/2, 3/5, 2/3第 3 个分数是2/5。示例 2Input: A [1, 7], K 1 Output: [1, 7]数据范围NoteA的长度在2到2000之间每个A[i]的值在1到30000之间K的取值范围是1到A.length * (A.length - 1) / 2即所有真分数的总数。这意味着最坏情况下分数数量约为2000 * 1999 / 2 ≈ 200 万暴力解法虽然可行但二分搜索才是符合大型输入规模的更优方案。解题思路总览原文档给出的核心思路可以归纳为两条主线暴力解法枚举所有可能的真分数(p, q)排序后直接输出第K小。注意排序时不能直接用浮点数比较必须转化为分子、分母的结构体用交叉相乘的方式比较大小避免浮点精度问题。最优解法二分搜索由于所有真分数都小于 1二分搜索范围是[0, 1]。每次取中点mid统计值小于mid的分数个数count并动态维护小于mid的分数中最大的那一个记录其分子与分母。根据count与K的大小关系收缩区间直到恰好找到第K小的分数。解法一暴力枚举 结构体排序O(n²)核心思想用两层循环枚举所有i j的组合(A[i], A[j])把每一对作为分子、分母存入结构体切片然后整体排序取第K - 1个元素即可。源码实现见仓库文件 leetcode/0786.K-th-Smallest-Prime-Fraction/786. K-th Smallest Prime Fraction.go核心代码如下// 解法二 暴力解法时间复杂度 O(n^2) func kthSmallestPrimeFraction1(A []int, K int) []int { if len(A) 0 || (len(A)*(len(A)-1))/2 K { return []int{} } fractions : []Fraction{} for i : 0; i len(A); i { for j : i 1; j len(A); j { fractions append(fractions, Fraction{molecule: A[i], denominator: A[j]}) } } sort.Sort(SortByFraction(fractions)) return []int{fractions[K-1].molecule, fractions[K-1].denominator} } // Fraction define type Fraction struct { molecule int denominator int } // SortByFraction define type SortByFraction []Fraction func (a SortByFraction) Len() int { return len(a) } func (a SortByFraction) Swap(i, j int) { a[i], a[j] a[j], a[i] } func (a SortByFraction) Less(i, j int) bool { return a[i].molecule*a[j].denominator a[j].molecule*a[i].denominator }关键细节为什么不能用 float 排序如果直接计算float64(p)/float64(q)再排序在数据量大、分数值非常接近时可能因浮点精度产生错误顺序。而SortByFraction.Less采用交叉相乘a[i].molecule * a[j].denominator a[j].molecule * a[i].denominator等价于比较a[i].molecule / a[i].denominator a[j].molecule / a[j].denominator全程使用整数运算杜绝精度误差。这正是原文档强调排序的时候不能直接用 float 排序需要转化成分子和分母的结构体进行排序的原因。边界处理源码在入口处做了两个防御判断输入数组为空len(A) 0K超过所有真分数的总数(len(A)*(len(A)-1))/2 K。此时直接返回空切片[]int{}对应测试用例 786. K-th Smallest Prime Fraction_test.go 中的边界分支验证// 覆盖暴力解法的边界分支空输入或 K 超过分数总数时返回空切片 if got : kthSmallestPrimeFraction1([]int{}, 1); len(got) ! 0 { t.Fatalf(kthSmallestPrimeFraction1([], 1) %v, want [], got) } if got : kthSmallestPrimeFraction1([]int{1, 2}, 5); len(got) ! 0 { t.Fatalf(kthSmallestPrimeFraction1([1 2], 5) %v, want [], got) }时间复杂度为O(n² log n)枚举O(n²)个分数 排序O(n² log n²)空间复杂度为O(n²)。解法二实数域二分搜索最优解核心思想因为所有真分数p/qp q都落在(0, 1)区间内所以可以在实数域[0, 1]上进行二分。对每个中点mid需要回答两个问题值严格小于mid的分数有多少个记为count这些小于mid的分数中最大的一个是谁记录其分子p、分母q。如果count K说明第K小的分数恰好就是当前维护的最大分数直接返回如果count K说明答案在更大的区间令low mid否则令high mid。源码实现// 解法一 二分搜索 func kthSmallestPrimeFraction(A []int, K int) []int { low, high, n : 0.0, 1.0, len(A) // 因为是在小数内使用二分查找无法像在整数范围内那样通过 mid1 和边界判断来终止循环 // 所以此处根据 count 来结束循环 for { mid, count, p, q, j : (highlow)/2.0, 0, 0, 1, 0 for i : 0; i n; i { for j n float64(A[i]) float64(mid)*float64(A[j]) { j } count n - j if j n q*A[i] p*A[j] { p A[i] q A[j] } } if count K { return []int{p, q} } else if count K { low mid } else { high mid } } }逐行拆解第 9 行二分区间初始化为[0.0, 1.0]n为数组长度。第 12 行由于是在实数域二分无法像整数二分那样通过mid1与边界判断终止循环因此以count是否恰好等于K作为循环出口注释中已明确说明这一点。第 13 行mid为区间中点count统计小于mid的分数个数p、q记录小于mid的最大分数的分子、分母初始为0/1j是指向分母的游标。第 14–23 行对每个分子A[i]利用数组有序性维护单调指针j只要A[i] mid * A[j]就右移j。此时A[i]/A[j] mid到A[i]/A[n-1]之间的分数都大于等于mid因此小于mid的分数个数为n - j累加到count。同时用交叉相乘q*A[i] p*A[j]判断并更新小于mid的最大分数。第 24–30 行count K直接返回count K说明第 K 小的分数比mid大缩小区间左边界否则缩小右边界。为什么用q*A[i] p*A[j]而不是浮点除法维护最大分数时同样采用整数交叉相乘A[i] / A[j] p / q等价于q * A[i] p * A[j]避免浮点误差保证最终返回的分子分母一定是数组中的精确元素。复杂度分析外层二分在实数域上进行收敛轮数与精度相关由于分数是有限个且来自有限数组实际只需迭代到某个count K的精确值即终止每次count统计中j指针单调递增单次统计为O(n)空间复杂度O(1)仅使用常数个变量。相比暴力解法的O(n²)空间二分搜索在空间上具有压倒性优势且时间上通常远快于枚举全部分数并排序。测试用例验证仓库测试文件 786. K-th Smallest Prime Fraction_test.go 覆盖了以下用例输入AK期望输出[1, 2, 3, 5]3[2, 5]对应题面示例[1, 7]1[1, 7]对应题面示例[1, 2]1[1, 2]最小规模[1, 2, 3, 5, 7]6[3, 7]测试同时调用两种解法并互相校验got : kthSmallestPrimeFraction1(p.A, p.K) if got[0] ! a.one[0] || got[1] ! a.one[1] { t.Fatalf(kthSmallestPrimeFraction1(%v, %d) %v, want %v, p.A, p.K, got, a.one) }注意此处二分解法直接作为输出打印暴力解法结果与期望答案比对外加对空输入与K越界两个边界分支的断言保证了暴力解法的健壮性。你可以按仓库统一的测试脚本运行验证go test ./leetcode/0786.K-th-Smallest-Prime-Fraction/... -v仓库根目录的 gotest.sh 展示了整个项目采用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...的方式进行全量覆盖率测试题解均要求 100% 测试覆盖。同系列题目已排序矩阵/序列中求第 K 小元素原文档明确指出这类在已排序的结构中寻找第 K 小元素的题目在仓库中有一个系列第 373 题Find K Pairs with Smallest Sums —— 从两个升序数组中找和最小的 K 个数对第 378 题Kth Smallest Element in a Sorted Matrix —— 在行列均升序的矩阵中找第 K 小元素仓库源码 378. Kth Smallest Element in a Sorted Matrix.go 同样提供了二分与堆两种实现第 668 题Kth Smallest Number in Multiplication Table —— 在乘法表中找第 K 小数字第 719 题Find K-th Smallest Pair Distance —— 在数组元素对的绝对差中找第 K 小距离第 786 题本题在素数真分数中找第 K 小分数。这类问题的通用套路是用单调计数函数回答小于等于/小于 x 的元素有多少个再配合值域二分逼近答案。786 题的独特点在于答案是一个分数需要额外维护小于 mid 的最大分数的分子分母这也是区分度最高的地方。小结维度暴力解法二分搜索解法时间复杂度O(n² log n)每轮O(n)轮数与值域收敛相关空间复杂度O(n²)O(1)精度风险需结构体交叉相乘规避全程整数交叉相乘无浮点比较适用规模小规模输入大规模输入n最大 2000实战建议作为题解理解暴力解法直观易写适合快速验证答案作为生产级实现优先采用二分搜索解法其在空间与时间上均显著更优。结合 README.md、题解源码 与 测试文件 三者对照阅读即可完整掌握本题的所有细节。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
