786 第 K 个最小的素数分数 「优先队列（堆）」&「

「这是我参与11月更文挑战的第 29 天，活动详情查看：2021最后一次更文挑战」。

题目描述

这是 LeetCode 上的 786. 第 K 个最小的素数分数 ，难度为困难。

Tag : 「优先队列」、「多路归并」、「二分」、「双指针」

给你一个按递增顺序排序的数组 arr 和一个整数 k 。

数组 arr 由 111 和若干素数组成，且其中所有整数互不相同。

对于每对满足 0<i<j<arr.length0 < i < j < arr.length0<i<j<arr.length 的 iii 和 jjj ，可以得到分数 arr[i]/arr[j]arr[i] / arr[j]arr[i]/arr[j] 。

那么第 kkk 个最小的分数是多少呢? 以长度为 222 的整数数组返回你的答案, 这里 answer[0]==arr[i]answer[0] == arr[i]answer[0]==arr[i] 且 answer[1]==arr[j]answer[1] == arr[j]answer[1]==arr[j] 。

示例 1：

ini复制代码输入：arr = [1,2,3,5], k = 3

输出：[2,5]

解释：已构造好的分数,排序后如下所示: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5

示例 2：

1
2
3

ini复制代码输入：arr = [1,7], k = 1

输出：[1,7]

提示：

2<=arr.length<=10002 <= arr.length <= 10002<=arr.length<=1000
1<=arr[i]<=3∗1041 <= arr[i] <= 3 * 10^41<=arr[i]<=3∗104
arr[0]==1arr[0] == 1arr[0]==1
arr[i]arr[i]arr[i] 是一个素数，i>0i > 0i>0
arrarrarr 中的所有数字互不相同，且按严格递增排序
1<=k<=arr.length∗(arr.length−1)/21 <= k <= arr.length * (arr.length - 1) / 21<=k<=arr.length∗(arr.length−1)/2

优先队列（堆）

数据范围只有 10310^3103，直接扫描所有点对的计算量不超过 10610^6106。

因此我们可以使用「扫描点对」+「优先队列（堆）」的做法，使用二元组 (arr[i],arr[j])(arr[i], arr[j])(arr[i],arr[j]) 进行存储，构建大小为 kkk 的大根堆。

根据「堆内元素多少」和「当前计算值与堆顶元素的大小关系」决定入堆行为：

若堆内元素不足 kkk 个，直接将当前二元组进行入堆；
若堆内元素已达 kkk 个，根据「当前计算值 arr[i]arr[j]\frac{arr[i]}{arr[j]}arr[j]arr[i] 与堆顶元素 peek[0]peek[1]\frac{peek[0]}{peek[1]}peek[1]peek[0] 的大小关系」进行分情况讨论：
- 如果当前计算值比堆顶元素大，那么当前元素不可能是第 kkk 小的值，直接丢弃；
- 如果当前计算值比堆顶元素小，那么堆顶元素不可能是第 kkk 小的值，使用当前计算值置换掉堆顶元素。

代码：

Java复制代码class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->Double.compare(b[0]*1.0/b[1],a[0]*1.0/a[1]));
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double t = arr[i] * 1.0 / arr[j];
                if (q.size() < k || q.peek()[0] * 1.0 / q.peek()[1] > t) {
                    if (q.size() == k) q.poll();
                    q.add(new int[]{arr[i], arr[j]});
                }
            }
        }
        return q.poll();
    }
}

时间复杂度：扫描所有的点对复杂度为 O(n2)O(n^2)O(n2)；将二元组入堆和出堆的复杂度为 O(log⁡k)O(\log{k})O(logk)。整体复杂度为 O(n2∗log⁡k)O(n^2 * \log{k})O(n2∗logk)
空间复杂度：O(k)O(k)O(k)

多路归并

在解法一中，我们没有利用「数组内元素严格单调递增」的特性。

由于题目规定所有的点对 (i,j)(i, j)(i,j) 必须满足 i<ji < ji<j，即给定 arr[j]arr[j]arr[j] 后，其所能构建的分数个数为 jjj 个，而这 jjj 个分数值满足严格单调递增：arr[0]arr[j]<arr[1]arr[j]<arr[2]arr[j]<…<arr[j−1]arr[j]\frac{arr[0]}{arr[j]} < \frac{arr[1]}{arr[j]} < \frac{arr[2]}{arr[j]} < … < \frac{arr[j - 1]}{arr[j]}arr[j]arr[0]<arr[j]arr[1]<arr[j]arr[2]<…<arr[j]arr[j−1]。

问题等价于我们从 n−1n - 1n−1 个（下标 000 作为分母的话，不存在任何分数）有序序列中找到第 kkk 小的数值。这 n−1n - 1n−1 个序列分别为：

[arr[0]arr[1]][\frac{arr[0]}{arr[1]}][arr[1]arr[0]]
[arr[0]arr[2],arr[1]arr[2]][\frac{arr[0]}{arr[2]}, \frac{arr[1]}{arr[2]}][arr[2]arr[0],arr[2]arr[1]]
[arr[0]arr[3],arr[1]arr[3],arr[2]arr[3]][\frac{arr[0]}{arr[3]}, \frac{arr[1]}{arr[3]}, \frac{arr[2]}{arr[3]}][arr[3]arr[0],arr[3]arr[1],arr[3]arr[2]]
…
[arr[0]arr[j],arr[1]arr[j],arr[2]arr[j],…,arr[j−1]arr[j]][\frac{arr[0]}{arr[j]}, \frac{arr[1]}{arr[j]}, \frac{arr[2]}{arr[j]}, … , \frac{arr[j - 1]}{arr[j]}][arr[j]arr[0],arr[j]arr[1],arr[j]arr[2],…,arr[j]arr[j−1]]

问题彻底切换为「多路归并」问题，我们使用「优先队列（堆）」来维护多个有序序列的当前头部的最小值即可。

代码：

Java复制代码class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{
            double i1 = arr[a[0]] * 1.0 / arr[a[1]], i2 = arr[b[0]] * 1.0 / arr[b[1]];
            return Double.compare(i1, i2);
        });
        for (int i = 1; i < n; i++) q.add(new int[]{0, i});
        while (k-- > 1) {
            int[] poll = q.poll();
            int i = poll[0], j = poll[1];
            if (i + 1 < j) q.add(new int[]{i + 1, j});
        }
        int[] poll = q.poll();
        return new int[]{arr[poll[0]], arr[poll[1]]};
    }
}

时间复杂度：起始将 n−1n - 1n−1 个序列的头部元素放入堆中，复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)；然后重复 kkk 次操作得到第 kkk 小的值，复杂度为 O(klog⁡n)O(k\log{n})O(klogn)。整体复杂度为 O(max⁡(n,k)∗log⁡n)O(\max(n, k) * \log{n})O(max(n,k)∗logn)
空间复杂度：O(n)O(n)O(n)

二分 + 双指针

进一步，利用 arrarrarr 递增，且每个点对 (i,j)(i, j)(i,j) 满足 i<ji < ji<j，我们可以确定 (i,j)(i, j)(i,j) 对应的分数 arr[i]arr[j]\frac{arr[i]}{arr[j]}arr[j]arr[i] 必然落在 [0,1][0, 1][0,1] 范围内。

假设最终答案 arr[i]arr[j]\frac{arr[i]}{arr[j]}arr[j]arr[i] 为 xxx，那么以 xxx 为分割点的数轴（该数轴上的点为 arrarrarr 所能构造的分数值）上具有「二段性」：

小于等于 xxx 的值满足：其左边分数值个数小于 kkk 个；
大于 xxx 的值不满足：其左边分数值个数小于 kkk 个（即至少有 kkk 个）。

而当确定 arr[j]arr[j]arr[j] 时，利用 arrarrarr 有序，我们可以通过「双指针」快速得知，满足 arr[i]arr[j]<=x\frac{arr[i]}{arr[j]} <= xarr[j]arr[i]<=x 的分子位置在哪（找到最近一个满足 arr[i]arr[j]>x\frac{arr[i]}{arr[j]} > xarr[j]arr[i]>x 的位置）。

另外，我们可以在每次 check 的同时，记录下相应的 arr[i]arr[i]arr[i] 和 arr[j]arr[j]arr[j]。

代码：

Java复制代码class Solution {
    double eps = 1e-8;
    int[] arr;
    int n, a, b;
    public int[] kthSmallestPrimeFraction(int[] _arr, int k) {
        arr = _arr;
        n = arr.length;
        double l = 0, r = 1;
        while (r - l > eps) {
            double mid = (l + r) / 2;
            if (check(mid) >= k) r = mid;
            else l = mid;
        }
        return new int[]{a, b};
    }
    int check(double x){
        int ans = 0;
        for (int i = 0, j = 1; j < n; j++) {
            while (arr[i + 1] * 1.0 / arr[j] <= x) i++;
            if (arr[i] * 1.0 / arr[j] <= x) ans += i + 1;
            if (Math.abs(arr[i] * 1.0 / arr[j] - x) < eps) {
                a = arr[i]; b = arr[j];
            }
        }
        return ans;
    }
}

时间复杂度：二分次数取决于精度，精度为 C=108C = 10^8C=108，二分复杂度为 O(log⁡C)；O(\log{C})；O(logC)；check 的复杂度为 O(n)O(n)O(n)。整体复杂度为 O(n∗log⁡C)O(n * \log{C})O(n∗logC)
空间复杂度：O(1)O(1)O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.786 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有