【面试高频题】难度 2.5/5，多解法经典面试笔试题
【面试高频题】难度 2.5/5，多解法经典面试笔试题
题目描述
这是 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]
优先队列（堆）
代码：
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})
- 空间复杂度：
多路归并
在解法一中，我们没有利用「数组内元素严格单调递增」的特性。
问题彻底切换为「多路归并」问题，我们使用「优先队列（堆）」来维护多个有序序列的当前头部的最小值即可。
代码：
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})
- 空间复杂度：
二分 + 双指针
进一步，利用 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}) - 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.786 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
