原文链接: https://leetcode-cn.com/problems/k-th-smallest-prime-fraction
英文原文
You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.
For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].
Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].
Example 1:
Input: arr = [1,2,3,5], k = 3 Output: [2,5] Explanation: The fractions to be considered in sorted order are: 1/5, 1/3, 2/5, 1/2, 3/5, and 2/3. The third fraction is 2/5.
Example 2:
Input: arr = [1,7], k = 1 Output: [1,7]
Constraints:
2 <= arr.length <= 10001 <= arr[i] <= 3 * 104arr[0] == 1arr[i]is a prime number fori > 0.- All the numbers of
arrare unique and sorted in strictly increasing order. 1 <= k <= arr.length * (arr.length - 1) / 2
中文题目
给你一个按递增顺序排序的数组 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 <= 10001 <= arr[i] <= 3 * 104arr[0] == 1arr[i]是一个 素数 ，i > 0arr中的所有数字 互不相同 ，且按 严格递增 排序1 <= k <= arr.length * (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) * \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)$
其他相关内容
1. 双指针
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
2. 二分
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
3. 堆
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 23. 合并K个升序链表 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 218. 天际线问题 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 264. 丑数 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 295. 数据流的中位数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 313. 超级丑数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 407. 接雨水 II | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
| 451. 根据字符出现频率排序 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 480. 滑动窗口中位数 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
| 502. IPO | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 692. 前K个高频单词 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 703. 数据流中的第 K 大元素 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 726. 原子的数量 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
| 786. 第 K 个最小的素数分数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 987. 二叉树的垂序遍历 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩🤩 |
| 1337. 矩阵中战斗力最弱的 K 行 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 1834. 单线程 CPU | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 面试题 17.14. 最小K个数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
4. 多路归并
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 21. 合并两个有序链表 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩🤩 |
| 264. 丑数 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 313. 超级丑数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 786. 第 K 个最小的素数分数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 24916 | 36882 | 67.6% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 有序矩阵中第 K 小的元素 | 中等 |
| 乘法表中第k小的数 | 困难 |
| 找出第 k 小的距离对 | 困难 |
