LeetCode 786. 第 K 个最小的质数分数
题目描述
题意分析
从严格递增的
arr中选下标i < j，组成分数arr[i] / arr[j]，将全部分数按数值从小到大排列，返回第k个分数的分子与分母原值。所有数均为正数，因此这些分数都在 $0$ 与 $1$ 之间。一共有 $n(n-1)/2$ 个合法下标对，不必先构造全部分数再排序。数组由
1和互不相同的质数组成，各个分数都已约分且彼此不同。下面先用小根堆按次序取数，再补充满足题目进阶要求的二分计数法。
解法：小根堆多路归并分数
核心思路
[!blue]
固定分子下标
i，让分母下标依次取n-1、n-2、…、i+1。分母逐渐减小，分数就严格增大，于是每个分子对应一条升序链；所有合法分数恰好分布在这n-1条链中。每条尚未耗尽的链只将最小未取项放入小根堆。链中后面的分数都不会小于链首，所以全体剩余分数的最小值，一定就是各链首中的最小值，也就是堆顶。
弹出
(i,j)后，这条链的下一项是(i,j-1)，只有j-1 > i时才存在；其他链的最小未取项没有变化，无需更新。这样每次弹出都是当前全局最小值，连续弹出k-1次后，堆顶就是第k小的分数。堆中保存下标对，比较时对正分母交叉相乘：
arr[i] / arr[j] < arr[x] / arr[y]等价于arr[i] * arr[y] < arr[x] * arr[j]。用long或int64计算乘积，便不需要把分数转换成浮点数。
解题步骤
- 对每个
i = 0..n-2，将(i,n-1)加入堆，建立各分子链的首项。- 重复
k-1次：取出堆顶(i,j)；若j-1 > i，就加入同一链的下一项(i,j-1)。- 读取剩余堆顶，并返回该下标对对应的数组值。
k == 1时不弹出任何元素；即使k取最大合法值，也只会弹出总数减一项，最后仍有一个候选可读取。题目保证k合法，因此不需要在正常流程中处理空堆结果。
代码实现
class Solution {
public int[] kthSmallestPrimeFraction(int[] arr, int k) {
int n = arr.length;
PriorityQueue<int[]> heap =
new PriorityQueue<>(
(a, b) -> {
// 交叉相乘比较分数，乘法前提升到宽整数
long left = (long) arr[a[0]] * arr[b[1]];
long right = (long) arr[b[0]] * arr[a[1]];
return Long.compare(left, right);
});
for (int i = 0; i < n - 1; i++) {
heap.offer(new int[] {
i,
n - 1
});
}
// 只移除前 k 减一项，剩余堆顶就是目标名次
for (int rank = 1; rank < k; rank++) {
int[] pair = heap.poll();
int i = pair[0];
int j = pair[1];
// 只推进刚弹出的分子链，分母下标仍须更大
if (j - 1 > i) {
heap.offer(new int[] {
i,
j - 1
});
}
}
int[] pair = heap.peek();
return new int[] {
arr[pair[0]],
arr[pair[1]]
};
}
}
import "container/heap"
type FractionPair struct {
i int
j int
}
type FractionHeap struct {
data []FractionPair
arr []int
}
func (h FractionHeap) Len() int { return len(h.data) }
func (h FractionHeap) Less(a int, b int) bool {
x := h.data[a]
y := h.data[b]
// 交叉相乘比较分数，乘法前提升到宽整数
left := int64(h.arr[x.i]) * int64(h.arr[y.j])
right := int64(h.arr[y.i]) * int64(h.arr[x.j])
return left < right
}
func (h FractionHeap) Swap(a int, b int) { h.data[a], h.data[b] = h.data[b], h.data[a] }
func (h *FractionHeap) Push(x any) { h.data = append(h.data, x.(FractionPair)) }
func (h *FractionHeap) Pop() any {
pair := h.data[len(h.data)-1]
h.data = h.data[:len(h.data)-1]
return pair
}
func kthSmallestPrimeFraction(arr []int, k int) []int {
h := &FractionHeap{arr: arr}
for i := 0; i < len(arr)-1; i++ {
h.data = append(h.data, FractionPair{i: i, j: len(arr) - 1})
}
heap.Init(h)
// 只移除前 k 减一项，剩余堆顶就是目标名次
for rank := 1; rank < k; rank++ {
pair := heap.Pop(h).(FractionPair)
// 只推进刚弹出的分子链，分母下标仍须更大
if pair.j-1 > pair.i {
heap.Push(h, FractionPair{i: pair.i, j: pair.j - 1})
}
}
pair := h.data[0]
return []int{
arr[pair.i],
arr[pair.j],
}
}
复杂度分析
- 时间复杂度：Java 为 $O((n+k)\log n)$；Go 批量建堆为 $O(n)$，后续 $O(k\log n)$。
- 空间复杂度：$O(n)$，每个分子最多一个活动候选。
当
k接近分数总数时，堆法最坏需要 $O(n^2\log n)$ 时间，不能满足小于 $O(n^2)$ 的进阶要求。下面用计数跳过整段排名。
关键点总结
[!green]
- 固定分子、递减分母才能形成升序链，堆始终保存每条链的最小未取项。
- 只推进刚弹出元素所在的链，既不会漏掉候选，也不会重复插入同一个下标对。
- 弹出
k-1项后查看堆顶；若已经弹出了k项，就应返回最后弹出项，不能再读堆顶。
解法二：整数阈值二分 + 双指针计数
核心思路
[!blue]
设
count(x)是不大于阈值 $x$ 的合法分数数量。阈值越大，数量越多，因此可以二分“第一个使数量至少为k的阈值”，而不用依次取出前k个分数。为了精确比较，令最大数组值为 $M$，取整数尺度 $D=M^2$，只考虑阈值 $t/D$，其中整数 $t$ 位于 $[0,D]$。任意两个不同分数 $a/b<c/d$ 的间距满足：
\[\frac{c}{d}-\frac{a}{b}=\frac{bc-ad}{bd}\ge\frac{1}{bd}\ge\frac{1}{M^2}\]所以每个网格区间 $((t-1)/D,t/D]$ 至多新包含一个分数。设最小的合格阈值为
t，它满足count((t-1)/D) < k、count(t/D) >= k，而数量最多增加一，因此后者恰好等于k。阈值下的最大分数就是答案，不需要设置浮点误差或把阈值本身当作答案。对一次计数，按分母下标
j从小到大扫描，用i表示满足arr[i] / arr[j] <= t/D的分子个数。比较条件改写为arr[i] * D <= t * arr[j]，并始终限制i < j。当分母增大，原先合格的分子仍然合格，所以i只向右移动；该分母贡献的分数数量就是i。若
i > 0，当前分母下的最大合格分数是arr[i-1] / arr[j]。将它与本轮记录的最大分数用交叉乘法比较，就能在计数的同时得到阈值下的最大分数。每当数量至少为k，保存这个分数并继续向更小的整数阈值搜索；最后一次保存时正好对应最小合格阈值。
解题步骤
- 令
D = arr[n-1]²，在整数闭区间[0,D]上二分。阈值0不包含分数，阈值D/D = 1包含全部合法分数。- 对中点
mid，重置i、累计数量和本轮最大分数；扫描所有分母，用单调右移的i统计不大于mid/D的分数。- 若数量小于
k，令left = mid+1；否则保存本轮最大分数，并令right = mid-1，继续寻找更小的合格阈值。- 区间为空后返回最后保存的分子和分母。
题目中 $M\le 3\times 10^4$，计数时的乘积最多达到 $M^3$，需要用
long或int64，并在乘法前完成类型提升。每轮最多统计 $n(n-1)/2$ 个分数，普通整数即可保存数量。
代码实现
class Solution {
public int[] kthSmallestPrimeFraction(int[] arr, int k) {
int n = arr.length;
long scale = (long) arr[n - 1] * arr[n - 1];
long left = 0;
long right = scale;
int[] answer = new int[2];
while (left <= right) {
long mid = left + (right - left) / 2;
int count = 0;
int i = 0;
int numerator = 0;
int denominator = 1;
for (int j = 1; j < n; j++) {
while (i < j && (long) arr[i] * scale <= mid * arr[j]) {
i++;
}
count += i;
if (i > 0
&& (long) arr[i - 1] * denominator > (long) numerator * arr[j]) {
numerator = arr[i - 1];
denominator = arr[j];
}
}
if (count >= k) {
answer[0] = numerator;
answer[1] = denominator;
right = mid - 1;
} else {
left = mid + 1;
}
}
return answer;
}
}
func kthSmallestPrimeFraction(arr []int, k int) []int {
n := len(arr)
scale := int64(arr[n-1]) * int64(arr[n-1])
left, right := int64(0), scale
answer := make([]int, 2)
for left <= right {
mid := left + (right-left)/2
count, i := 0, 0
numerator, denominator := 0, 1
for j := 1; j < n; j++ {
for i < j && int64(arr[i])*scale <= mid*int64(arr[j]) {
i++
}
count += i
if i > 0 && int64(arr[i-1])*int64(denominator) > int64(numerator)*int64(arr[j]) {
numerator = arr[i-1]
denominator = arr[j]
}
}
if count >= k {
answer[0] = numerator
answer[1] = denominator
right = mid - 1
} else {
left = mid + 1
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n\log M)$。整数二分范围大小为 $M^2+1$，迭代次数为 $O(\log M)$；每次扫描中分母与分子指针都只前进 $O(n)$ 次。
- 空间复杂度：$O(1)$，只维护二分边界、计数、两个指针和一个候选分数。
关键点总结
[!green]
- 二分的是精确的整数阈值，利用分数间距下界，保证最小合格阈值只包含前
k个分数。- 分母从小到大时，合格分子的数量不减，因此每轮计数可以用一个不回退的指针完成。
- 保存真实的分子和分母，阈值只用于计数，返回值不需要做任何近似还原。
易错点总结
[!yellow]
- 分母下标允许等于分子，会混入非法的一。
- 只初始化一条链，会漏掉其他分子。
- 推进其他链，破坏每链最小未取项的含义。
- 二分计数时，每换一个阈值都要重置
i和累计数量；只有同一阈值下扫描不同分母时，才能复用单调右移的i。- 先用普通整数算完乘积再转为宽整数，可能已经溢出；尺度计算和阈值比较都要在乘法前提升类型。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 373. 查找和最小的 K 对数字 | 中等 | 同样在隐式有序数对中求前k项，可按一侧固定形成多路候选并用堆归并。 |
| 378. 有序矩阵中第 K 小的元素 | 中等 | 同样可二分数值并计不超过阈值的候选，本题候选为有效下标对的分数而非完整矩阵格子。 |