题目大意：
第 K 个最小的素数分数
一个已排序好的表 A，其包含 1 和其他一些素数. 当列表中的每一个 p<q 时，我们可以构造一个分数 p/q 。
那么第 k 个最小的分数是多少呢? 以整数数组的形式返回你的答案, 这里 answer[0] = p 且 answer[1] = q.
示例: 输入: A = [1, 2, 3, 5], K = 3 输出: [2, 5] 解释: 已构造好的分数,排序后如下所示: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3. 很明显第三个最小的分数是 2/5.
输入: A = [1, 7], K = 1 输出: [1, 7]
注意:
- A 的取值范围在 2 — 2000.
- 每个 A[i] 的值在 1 —30000.
- K 取值范围为 1 —A.length * (A.length – 1) / 2
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=786
解题思路分析：
题目给出的数组已经按照升序方式排列好，因此我们可以快速的得知，数组中第一个数与最后一个数组成的分数一定是最小的，而第二小的可能是第一个数与倒数第二个数组成的分数N1，或者是第二个数与最后一个数组成的分数N2，到这一步我们就无法再继续判断下去了。因此，解题时，我们可以建立一个PriorityQueue，按照大小顺序来存储所有分数，然后取出第K个元素就是第K小的分数。
不过这样做需要将所有分数都列举出来，大概率会超时。所以我们可以考虑先将所有数字与第一个数字组成的分数存入Queue。接下来从Queue中取出第一个元素，它一定最小的那个（首元素与尾元素组成的分数），然后我们将这个元素的分子向后移动一位，即利用第二个元素与尾元素组成一个新的分数，这个分数是稍微大于最小分数的一个数字，也是上文提到过的N2，我们将它插入到Queue中，这时Queue中一定存在N1和N2两个相对最小的分数，我们再从Queue中取出最小的一个，重复上述过程，直到第K次取出的元素即是本题的解。
实现代码：
public int[] kthSmallestPrimeFraction(int[] A, int K) {
// 排序用的Queue，
// Queue中存储的是分子index，分母index，以及分数的值
PriorityQueue<double[]> q
=new PriorityQueue<>((a,b)->a[2]-b[2]>0?1:-1);
// 将所有数数字与首元素组成的分数存入Queue
for(int i=1;i<A.length;i++){
q.offer(new double[]{0,i,(double)A[0]/A[i]});
}
// 返回结果
int[] res=new int[2];
// 循环K次，每次从Queue中取出最小元素
for(int i=1;i<=K;i++){
// 取出最小元素
double[] arr=q.poll();
// 如果当前是第K次，
if(i==K){
// 将当前元素的分子与分母下标赋值到返回结果
res[0]=A[(int)arr[0]];
res[1]=A[(int)arr[1]];
break;
}
// 将分子对应数组中的下标变大一位
arr[0]++;
// 重新计算当前分数的值
arr[2]=(double)A[(int)arr[0]]/A[(int)arr[1]];
// 将当前分数加入Queue
q.offer(arr);
}
return res;
} 本题解法执行时间为821ms。
Runtime: 821 ms, faster than 23.97% of Java online submissions for K-th Smallest Prime Fraction.
Memory Usage: 41.6 MB, less than 33.33% of Java online submissions for K-th Smallest Prime Fraction.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-786-k-th-smallest-prime-fraction-解题思路分析/