Formatted question description: https://leetcode.ca/all/786.html
786. K-th Smallest Prime Fraction
Level
Hard
Description
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 between2
and2000
.- Each
A[i]
will be between1
and30000
. K
will be between1
andA.length * (A.length - 1) / 2
.
Solution
Use a priority queue to store the fractions, where the smallest fraction is polled first. Initially, offer all [A[0], A[i]]
where 0 < i < A.length
to the priority queue. Since A[0]
is 1 and the smallest fraction has a numerator 1, the smallest fraction is in the priority queue.
Then poll the smallest fraction from the priority queue for K - 1
times. To ensure that the remaining smallest fraction is in the priority queue, each time a fraction is polled, try to find the next smallest fraction and offer it to the priority queue if it exists. Suppose the fraction polled is [A[i], A[j]]
where 0 <= i < j < A.length
. If i + 1 < j
, then offer the new fraction [A[i + 1], A[j]]
to the priority queue.
After the K - 1
times, the next element to be polled from the priority queue is the K
-th smallest prime fraction, so return the fraction.
class Solution {
public int[] kthSmallestPrimeFraction(int[] A, int K) {
Map<Integer, Integer> numIndexMap = new HashMap<Integer, Integer>();
int length = A.length;
for (int i = 0; i < length; i++)
numIndexMap.put(A[i], i);
PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] fraction1, int[] fraction2) {
return fraction1[0] * fraction2[1] - fraction2[0] * fraction1[1];
}
});
for (int i = 1; i < length; i++) {
int[] fraction = {A[0], A[i]};
priorityQueue.add(fraction);
}
for (int i = 1; i < K; i++) {
int[] fraction = priorityQueue.poll();
int numeratorIndex = numIndexMap.get(fraction[0]), denominatorIndex = numIndexMap.get(fraction[1]);
if (numeratorIndex + 1 < denominatorIndex) {
numeratorIndex++;
int[] newFraction = {A[numeratorIndex], fraction[1]};
priorityQueue.offer(newFraction);
}
}
return priorityQueue.peek();
}
}