企业官网建设流程全解析

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] = p，answer[1] = q。

示例 1：

Input: 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。

示例 2：

Input: A = [1, 7], K = 1 Output: [1, 7]

数据范围（Note）

• A的长度在2到2000之间；
• 每个A[i]的值在1到30000之间；
• K的取值范围是1到A.length * (A.length - 1) / 2（即所有真分数的总数）。

这意味着最坏情况下分数数量约为2000 * 1999 / 2 ≈ 200 万，暴力解法虽然可行，但二分搜索才是符合大型输入规模的更优方案。

解题思路总览

原文档给出的核心思路可以归纳为两条主线：

1. 暴力解法：枚举所有可能的真分数(p, q)，排序后直接输出第K小。注意排序时不能直接用浮点数比较，必须转化为分子、分母的结构体，用交叉相乘的方式比较大小，避免浮点精度问题。
2. 最优解法（二分搜索）：由于所有真分数都小于 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) == 0）；
• K超过所有真分数的总数（(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/q（p < q）都落在(0, 1)区间内，所以可以在实数域[0, 1]上进行二分。对每个中点mid，需要回答两个问题：

1. 值严格小于mid的分数有多少个（记为count）；
2. 这些小于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) // 因为是在小数内使用二分查找，无法像在整数范围内那样通过 mid+1 和边界判断来终止循环 // 所以此处根据 count 来结束循环 for { mid, count, p, q, j := (high+low)/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 行：由于是在实数域二分，无法像整数二分那样通过mid+1与边界判断终止循环，因此以count是否恰好等于K作为循环出口（注释中已明确说明这一点）。
• 第 13 行：mid为区间中点；count统计小于mid的分数个数；p、q记录小于mid的最大分数的分子、分母（初始为0/1）；j是指向分母的游标。
• 第 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 覆盖了以下用例：

测试同时调用两种解法并互相校验：

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 -covermode=atomic -coverprofile=coverage.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 的最大分数"的分子分母，这也是区分度最高的地方。

小结

实战建议：作为题解理解，暴力解法直观易写，适合快速验证答案；作为生产级实现，优先采用二分搜索解法，其在空间与时间上均显著更优。结合 README.md、题解源码 与 测试文件 三者对照阅读，即可完整掌握本题的所有细节。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go