题目形容
这是 LeetCode 上的 786. 第 K 个最小的素数分数 ，难度为 中等。
Tag : 「优先队列（堆）」、「多路归并」、「二分」、「双指针」
给你一个按递增程序排序的数组 arr 和一个整数 k 。
数组 arr 由 $1$ 和若干 素数 组成，且其中所有整数互不雷同。
对于每对满足 $0 < i < j < arr.length$ 的 $i$ 和 $j$ ，能够失去分数 $arr[i] / arr[j]$ 。
那么第 $k$ 个最小的分数是多少呢? 以长度为 $2$ 的整数数组返回你的答案, 这里 $answer[0] == arr[i]$ 且 $answer[1] == arr[j]$ 。
示例 1：
输出：arr = [1,2,3,5], k = 3输入：[2,5]解释：已结构好的分数,排序后如下所示: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3很显著第三个最小的分数是 2/5示例 2：
输出：arr = [1,7], k = 1输入：[1,7]提醒：
- $2 <= arr.length <= 1000$
- $1 <= arr[i] <= 3 \times 10^4$
- $arr[0] = 1$
- $arr[i]$ 是一个 素数 ，$i > 0$
- $arr$ 中的所有数字 互不雷同 ，且按严格递增排序
- $1 <= k <= arr.length \times (arr.length - 1) / 2$
优先队列（堆）
数据范畴只有 $10^3$，间接扫描所有点对的计算量不超过 $10^6$。
因而咱们能够应用「扫描点对」+「优先队列（堆）」的做法，应用二元组 $(arr[i], arr[j])$ 进行存储，构建大小为 $k$ 的大根堆。
依据「堆内元素多少」和「以后计算值与堆顶元素的大小关系」决定入堆行为：
- 若堆内元素有余 $k$ 个，间接将以后二元组进行入堆；
若堆内元素已达 $k$ 个，依据「以后计算值 $\frac{arr[i]}{arr[j]}$ 与堆顶元素 $\frac{peek[0]}{peek[1]}$ 的大小关系」进行分状况探讨：
- 如果以后计算值比堆顶元素大，那么以后元素不可能是第 $k$ 小的值，间接抛弃；
- 如果以后计算值比堆顶元素小，那么堆顶元素不可能是第 $k$ 小的值，应用以后计算值置换掉堆顶元素。
代码：
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(n^2)$；将二元组入堆和出堆的复杂度为 $O(\log{k})$。整体复杂度为 $O(n^2\log{k})$
- 空间复杂度：$O(k)$
多路归并
在解法一中，咱们没有利用「数组内元素严格枯燥递增」的个性。
因为题目规定所有的点对 $(i, j)$ 必须满足 $i < j$，即给定 $arr[j]$ 后，其所能构建的分数个数为 $j$ 个，而这 $j$ 个分数值满足严格枯燥递增：$\frac{arr[0]}{arr[j]} < \frac{arr[1]}{arr[j]} < \frac{arr[2]}{arr[j]} < ... < \frac{arr[j - 1]}{arr[j]}$。
问题等价于咱们从 $n - 1$ 个（下标 $0$ 作为分母的话，不存在任何分数）有序序列中找到第 $k$ 小的数值。这 $n - 1$ 个序列别离为：
- $[\frac{arr[0]}{arr[1]}]$
- $[\frac{arr[0]}{arr[2]}, \frac{arr[1]}{arr[2]}]$
- $[\frac{arr[0]}{arr[3]}, \frac{arr[1]}{arr[3]}, \frac{arr[2]}{arr[3]}]$
... - $[\frac{arr[0]}{arr[j]}, \frac{arr[1]}{arr[j]}, \frac{arr[2]}{arr[j]}, ... , \frac{arr[j - 1]}{arr[j]}]$
问题彻底切换为「多路归并」问题，咱们应用「优先队列（堆）」来保护多个有序序列的以后头部的最小值即可。
代码：
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 - 1$ 个序列的头部元素放入堆中，复杂度为 $O(n\log{n})$；而后反复 $k$ 次操作失去第 $k$ 小的值，复杂度为 $O(k\log{n})$。整体复杂度为 $O(\max(n, k) \times \log{n})$
- 空间复杂度：$O(n)$
二分 + 双指针
进一步，利用 $arr$ 递增，且每个点对 $(i, j)$ 满足 $i < j$，咱们能够确定 $(i, j)$ 对应的分数 $\frac{arr[i]}{arr[j]}$ 必然落在 $[0, 1]$ 范畴内。
假如最终答案 $\frac{arr[i]}{arr[j]}$ 为 $x$，那么以 $x$ 为宰割点的数轴（该数轴上的点为 $arr$ 所能结构的分数值）上具备「二段性」：
- 小于等于 $x$ 的值满足：其右边分数值个数小于 $k$ 个；
- 大于 $x$ 的值不满足：其右边分数值个数小于 $k$ 个（即至多有 $k$ 个）。
而当确定 $arr[j]$ 时，利用 $arr$ 有序，咱们能够通过「双指针」疾速得悉，满足 $\frac{arr[i]}{arr[j]} <= x$ 的分子地位在哪（找到最近一个满足 $\frac{arr[i]}{arr[j]} > x$ 的地位）。
另外，咱们能够在每次 check 的同时，记录下相应的 $arr[i]$ 和 $arr[j]$。
代码：
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 = 10^8$，二分复杂度为 $O(\log{C})；$
check的复杂度为 $O(n)$。整体复杂度为 $O(n\log{C})$ - 空间复杂度：$O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.786 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布