786. K-th Smallest Prime Fraction 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        Queue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            double d1 = arr[o1[0]] * 1.0 / arr[o1[1]];
            double d2 = arr[o2[0]] * 1.0 / arr[o2[1]];
            return Double.compare(d1, d2);
        });

        // 把所有队列头部入堆
        // 如：arr = [1, 2, 3, 5]
        // 拆分为三个队列：
        // 队列一：1/2
        // 队列二：1/3, 2/3
        // 队列三：1/5, 2/5, 3/5
        // 以上三个队列单调自增
        for (int i = 1; i < arr.length; i++) {
            queue.offer(new int[]{0, i});
        }

        // k 大于 1 能保证 kth 在堆顶，以便于最后收集
        while (k > 1) {
            int[] index = queue.poll();
            int i = index[0], j = index[1];
            if (i + 1 < j) {
                queue.offer(new int[]{i + 1, j});
            }

            k--;
        }

        int[] kth = queue.poll();
        return new int[]{arr[kth[0]], arr[kth[1]]};
    }
}

References

786. K-th Smallest Prime Fraction