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

``````class Solution {
public:
vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
priority_queue<pair<double, pair<int, int>>> q;
for (int i = 0; i < A.size(); ++i) {
q.push({-1.0 * A[i] / A.back(), {i, A.size() - 1}});
}
while (--K) {
auto t = q.top().second; q.pop();
--t.second;
q.push({-1.0 * A[t.first] / A[t.second], {t.first, t.second}});
}
return {A[q.top().second.first], A[q.top().second.second]};
}
};
``````

``````class Solution {
public:
vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
double left = 0, right = 1;
int p = 0, q = 1, cnt = 0, n = A.size();
while (true) {
double mid = left + (right - left) / 2.0;
cnt = 0; p = 0;
for (int i = 0, j = 0; i < n; ++i) {
while (j < n && A[i] > mid * A[j]) ++j;
cnt += n - j;
if (j < n && p * A[j] < q * A[i]) {
p = A[i];
q = A[j];
}
}
if (cnt == K) return {p, q};
if (cnt < K) left = mid;
else right = mid;
}
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/786

Find K Pairs with Smallest Sums

Kth Smallest Element in a Sorted Matrix

Kth Smallest Number in Multiplication Table

Find K-th Smallest Pair Distance

https://leetcode.com/problems/k-th-smallest-prime-fraction/discuss/115531/C++-9lines-priority-queue

https://leetcode.com/problems/k-th-smallest-prime-fraction/discuss/115819/Summary-of-solutions-for-problems-%22reducible%22-to-LeetCode-378

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation