786-K-th Smallest Prime Fraction

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

---

问题描述: 有序列表A含有1还有一些素数。对于列表中的每个 p<q p < q ,我们考虑它们的分数 pq p q 第k个最小的分数是？结果以数组形式返回，数组的第一个元素为p，第二个元素为q。

---

问题分析: 请仔细看一下这个链接: https://leetcode.com/problems/k-th-smallest-prime-fraction/discuss/115819/Summary-of-solutions-for-problems-"reducible"-to-LeetCode-378 相信对你的帮助会很大

---

解法:

class Solution { public int[] kthSmallestPrimeFraction(int[] A, int K) { double lo = 0.0, hi = 1.0; int[] ans = {-1, -1}; while (hi-lo > 1e-9) { // 一直压缩精确度到1e-9 double mid = lo + (hi - lo) / 2.0; int[] res = under(A, mid); if (res[2] < K) { lo = mid; } else { hi = mid; ans[0] = res[0]; ans[1] = res[1]; } } return ans; } private int[] under(int[] A, double bound) { // 计算有多少数小于bound int mol = 0, deno = 1, count = 0, i = -1; for (int j = 1; j < A.length; j++) { while (A[i + 1] < bound * A[j]) i++; count += i + 1; if (i >= 0 && mol * A[j] < deno * A[i]) { mol = A[i]; deno = A[j]; } } return new int[]{mol, deno, count}; } }