题目描述：

LeetCode 786. K-th Smallest Prime Fraction

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`.

解题思路：

```首先将下标(0, 1), (0, 2) ... (0, N)加入优先队列pq，pq中的数对(i, j)按照A[i] / A[j]从小到大排序

Java代码：

``````public class Solution {

public int[] kthSmallestPrimeFraction(int[] A, int K) {

class Pair implements Comparable<Pair>{
public int x;
public int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
public int compareTo(Pair p) {
return A[x] * A[p.y] - A[y] * A[p.x];
}
}

PriorityQueue<Pair> pq = new PriorityQueue<>();
for (int i = 1; i < A.length; i++) {
}
Pair top = null;
for (int i = 0; i < K; i++) {
top = pq.poll();
if (top.x + 1 < top.y) {
}
}
return new int[]{A[top.x], A[top.y]};
}

}
``````

Python代码（Time Limit Exceeded）

``````class Solution(object):
def kthSmallestPrimeFraction(self, A, K):
"""
:type A: List[int]
:type K: int
:rtype: List[int]
"""
N = len(A)
h = []
for i in range(1, N):
heapq.heappush(h, (float(A[0]) / A[i], 0, i))
for x in range(K):
v, p, q = heapq.heappop(h)
if p + 1 < q:
heapq.heappush(h, (float(A[p + 1]) / A[q], p + 1, q))
return A[p], A[q]
``````

Pingbacks已关闭。