K-th Smallest Prime Fraction-LeetCode#786

A sorted list A contains 1, plus some number of primes.  Then, for every p < q in the list, we consider the fraction p/q.
What is the K-th smallest fraction considered?  Return your answer as an array of ints, where answer[0] = p and answer[1] = q.

Examples:
Input: A = [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, 2/3.
The third fraction is 2/5.
Input: A = [1, 7], K = 1
Output: [1, 7]

Note:

• A will have length between 2 and 2000.
• Each A[i] will be between 1 and 30000.
• K will be between 1 and A.length * (A.length - 1) / 2.

思路：看到这题第一个想到的是每次循环然后把相除的结果(key)和相除的两个数(value)为键值对存进Map，单独把相除的结果存入List，在List排序后取到第K个值。
再从map.get(key)获取相除的两个数。

public class KthSmallestPrimeFraction {
    public int[] kthSmallestPrimeFraction(int[] A, int K) {
        int[] res = null;
        List<Double> primeList = new ArrayList<>();
        Map<Double, int[]> map = new HashMap<>();
        for (int i = 0; i < A.length - 1; i++){
            for (int j = i + 1;j < A.length ; j++){
                int[] tempList = {A[i], A[j]};
                double temp = (double) A[i]/A[j];
                map.put(temp, tempList);
                primeList.add(temp);
            }
        }
        Collections.sort(primeList);
        return map.get(primeList.get(K - 1));
    }
    public static void main(String[] args) {
        int[] A = {1, 2, 3, 5};
        KthSmallestPrimeFraction kthSmallestPrimeFraction = new KthSmallestPrimeFraction();
        kthSmallestPrimeFraction.kthSmallestPrimeFraction(A,3);
    }
}

很明显，超时啦啦啦啦啦….
vote最高的解答：

public int[] kthSmallestPrimeFraction(int[] A, int K) {
    int n = A.length;
    PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
        public int compare(int[] a, int[] b) {
            return Integer.compare(A[a[0]] * A[n - 1 - b[1]], A[n - 1 - a[1]] * A[b[0]]);
        }
    });
    for (int i = 0; i < n; i++) {
        pq.offer(new int[] {i, 0});
    }
    while (--K > 0) {
        int[] p = pq.poll();
        if (++p[1] < n) {
            pq.offer(p);
        }
    }
    return new int[] {A[pq.peek()[0]], A[n - 1 - pq.peek()[1]]};
}