LeetCode 786. 第 K 个最小的质数分数

2023-08-16 HGNULB 约 7 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 786. 第 K 个最小的质数分数

题意分析

给一个严格递增的数组 arr，首元素是 1，其余都是质数。把所有满足 i < j 的下标对拿出来组成分数 arr[i] / arr[j]，要求返回其中第 k 小的那个分数，返回形式是长度为 2 的数组 [分子, 分母]——注意要的是原始的两个数值，不是浮点结果。

候选对共有 $n(n-1)/2$ 个。约束里 $n \le 1000$，也就是最多约 50 万个候选，k 的上界就是这个数量。把所有分数生成出来排序是 $O(n^2 \log n)$，在这个数据量下其实跑得动，但它没有利用数组已经有序这个前提，面试里会被直接追问「有序性用了吗」。

有序性给出的信号非常明确：固定分子下标 i，让分母下标 j 从 n-1 往左走，分母变小、分数单调变大。于是全体候选自然分成了 $n-1$ 条各自有序的链，问题变成「从若干条有序链里取第 k 小」，这类形状有成熟的处理套路。另一个信号来自「第 k 小」加上「所有元素互质、值域有限」，也允许把答案当成一个实数去二分并数出小于它的分数个数。

边界要盯住：分子分母不能同下标，必须严格 i < j；arr 中含 1 与质数，任意两个不同元素互质，所以所有分数两两不等，不存在并列名次的歧义；比较两个分数时不能用浮点除法，arr[i] 可达 3 万量级，除法结果的相对差可能小到浮点精度之下。

解法：小根堆多路归并分数

核心思路

固定分子下标 i，合法分数按下面的顺序严格递增：
\[\frac{arr[i]}{arr[n-1]} < \frac{arr[i]}{arr[n-2]} < \cdots < \frac{arr[i]}{arr[i+1]}\]
因此全部分数可以看成 $n-1$ 条升序链，问题等价于从多条有序链中取第 k 小。小根堆中只保留每条链当前最小的未取分数：先放入所有 (i, n-1)；弹出 (i, j) 后，再放入同一条链的 (i, j-1)。

堆不变量：每轮开始时，堆中恰好有每条未耗尽链的队首。任意未取元素都不会小于它所在链的队首，所以堆顶一定是全局最小的未取分数。弹出后只补入该链的新队首，不变量继续成立；因此弹出 k-1 次后，新的堆顶就是第 k 小。

堆中存下标而不是浮点值。比较 $arr[a]/arr[b]$ 与 $arr[c]/arr[d]$ 时，比较 arr[a] * arr[d] 和 arr[c] * arr[b]。代码先转成 long / int64 再乘，既没有浮点精度问题，也避免把这套写法迁移到更大值域时发生整数溢出。

解题步骤

建立小根堆，元素为分子、分母的下标对 (i, j)，比较器使用整数交叉相乘。

对 i = 0...n-2，将 (i, n-1) 入堆；它是第 i 条链的最小值。

重复 k-1 次：弹出堆顶 (i, j)；若 j-1 > i，将 (i, j-1) 入堆。严格大于是为了始终满足分子下标小于分母下标。

返回当前堆顶对应的 [arr[i], arr[j]]。

例如 arr = [1, 2, 3, 5]、k = 3。初始候选是 1/5、2/5、3/5；弹出 1/5 后补入 1/3，再弹出 1/3 后补入 1/2，此时堆顶为 2/5，所以答案是 [2, 5]。

代码实现

import java.util.PriorityQueue;

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});
        }

        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)

    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]}
}

复杂度分析

时间复杂度：$O(n \log n + k \log n)$，可写成 $O((n+k)\log n)$。堆中最多有 $n-1$ 个元素，初始化逐个入堆和随后至多 k-1 次弹出、插入都以 $O(\log n)$ 为上界。Go 代码先批量写入再 heap.Init，其初始化实际为 $O(n)$。

空间复杂度：$O(n)$。每条链在堆中至多保留一个候选，没有生成全部 $O(n^2)$ 个分数。

关键点总结

先识别“固定分子后有序”，再把二维候选转成多路归并；堆只是维护各链队首的工具。

弹出哪个候选，就只推进它所属的链，这是维持堆不变量的关键。

分数比较用交叉相乘，不用浮点数；乘法前转换为更宽的整数类型。

小根堆适合直接取前 k 个；若面试官继续追问，还可讨论“答案二分 + 双指针计数”，但无需同时维护两套实现。

易错点总结

用浮点数作堆比较键：相近分数可能因精度损失得到错误顺序，应使用交叉相乘。

先乘再强转：(long) (a * d) 仍会先按 int 计算并溢出；必须写成 (long) a * d。Go 同理要在乘法前转成 int64。

边界写成 j-1 >= i：会把 (i, i) 这种非法的 1 放进堆；合法条件必须是 j-1 > i。

只初始化一条链或推进错链：会漏掉候选，堆顶不再代表全局最小未取分数。

名次少弹或多弹一次：这里弹出 k-1 次再读取堆顶；若选择弹出 k 次，则应返回最后一次弹出的元素，不能混用两种写法。

相似题目

题目	难度	考察点
373. 查找和最小的 K 对数字	中等	同为二维取第 k 小，但两维都可推进，入堆时要用集合去重或只从一维推进
378. 有序矩阵中第 K 小的元素	中等	链是矩阵的行，除堆外还能对值域二分并逐行统计，是二分解法的入门题
23. 合并 K 个升序链表	困难	多路归并要取全部而非第 k 个，链表形态下推进就是 `next` 指针
719. 找出第 K 小的数对距离	困难	候选数量同为 $O(n^2)$ 但 k 可极大，堆会退化，只能二分距离配合双指针计数
668. 乘法表中第k小的数	困难	矩阵不显式存在，只能按公式二分并对每行 $O(1)$ 计数
264. 丑数 II	中等	三条链由乘 2、3、5 生成，元素会重复，推进时要同时移动所有命中的指针
632. 最小区间	困难	同样用堆维护每条链的队首，但目标是覆盖全部链的最小区间而非第 k 小
215. 数组中的第K个最大元素	中等	一维无序数据取第 k 大，堆只是备选，快速选择能做到期望 $O(n)$
LCR 061. 查找和最小的 K 对数字	中等	与 373 同题，可直接套用本题的「只沿一维推进」写法