LeetCode刷题【786】第 K 个最小的素数分数

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

输入：arr = [1,7], k = 1
输出：[1,7]

优先队列两种实现

首先，直接上来一个优先队列，自定义排序。

为了实现这个自定义的排序，我们需要记录几个东西

1. 分子
2. 分母
3. 为了便于比较，相除后的小数值也可以事先计算好，比较的时候就直接比较这个数字即可
4. 把所有的都放进去之后，我们就开始从头部取出K个即可
5. 最终得到第K个的分子分母即可

理解起来也相对比较简单

代码

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<double[]> queue = new PriorityQueue<>(new Comparator<double[]>() {
            @Override
            public int compare(double[] o1, double[] o2) {
                if (o1[2] >= o2[2]){
                    return 1;
                }
                return -1;
            }
        });
        for (int i : arr) {
            for (int j : arr) {
                queue.offer(new double[]{(double)i,(double)j,((double)i)/j});
            }
        }
        while (--k > 0){
            queue.poll();
        }
        return new int[]{(int)queue.peek()[0],(int)queue.peek()[1]};
    }
}

写完这个之后思考一下，我们真的需要把所有的值都算一遍全都存进优先队列么？答案是否定的，

1. 我们可以把数据分别按照分母分成arr[]数组长度个分组，
2. 分别维护一个指针，指向当前对应的分子，
3. 这样我们的优先队列只要维护比较arr[]数组长度个值即可，每当从队列头部取出一个对象时，只需把分子位置往后挪动一位，重新放入队列
4. 如果分子指针位置已经到达了arr[]数组尾部，则不再需要往队列中添加

代码

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (((double)arr[o1[0]])/arr[o1[1]] >= ((double)arr[o2[0]])/arr[o2[1]]){
                    return 1;
                }
                return -1;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            queue.offer(new int[]{0,i});
        }
        while (--k > 0) {
            int[] top = queue.poll();
            if (top[0] < arr.length){
                top[0]++;
                queue.offer(top);
            }
        }
        return new int[]{arr[queue.peek()[0]],arr[queue.peek()[1]]};
    }

}