[LeetCode 786. 第 K 个最小的素数分数] 嵌套二分

1. 题目链接

2. 题目描述

一个已排序好的表 A，其包含 1 和其他一些素数. 当列表中的每一个 $p\lt q$ 时，我们可以构造一个分数 $p/q$ 。

那么第 k 个最小的分数是多少呢? 以整数数组的形式返回你的答案, 这里 answer[0] = p 且 answer[1] = q.

示例:
输入: A = [1, 2, 3, 5], K = 3
输出: [2, 5]
解释:
已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3.
很明显第三个最小的分数是 2/5.

输入: A = [1, 7], K = 1
输出: [1, 7]

注意:

- A 长度的取值范围在 2~2000.
- 每个 A[i] 的值在 1~30000.
- K 取值范围为 1~A.length*(A.length-1)/2

3. 解题思路

嵌套二分。首先二分分数值 $x$，对于二分的每个 $x$，求解 $\mathcal S={(p,q))|\frac{p}{q}\lt x\mbox{ and }p\lt q }$ 的大小，通过比较集合与K的大小关系，找到第k小分数值。

计算 $|\mathcal S|$，也是通过二分来做。枚举分母 $q$，求数组中有多少个数小于等于 $x*q$。

复杂度 $\mathcal O(n\log n\log L)$。$L$ 是分数的数值表示范围。

4. 参考代码

class Solution {
public:
    int get_size(vector<int>& A, long double val) {
        int cnt = 0;
        for(auto& q : A) {
            cnt += upper_bound(A.begin(), A.end(), val*q)-A.begin();
        }
        return cnt;
    }
    const long double eps = 1e-10;
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
        long double lb = 0, ub = 1;
        long double x = 0;
        while(fabs(ub - lb) > eps) {
            long double md = (lb + ub) * 0.5;
            int cnt = get_size(A, md);
            if(cnt < K) {
                lb = md;
            } else {
                x = md;
                ub = md;
            }
        }
        unordered_set<int> st;
        int ansp = -1, ansq = A[0];
        for(auto& q: A) {
            long double p = q * x;
            if(fabs(p - int(p)) < 1e-2 && \
               st.find((int) p) != st.end() && \
               get_size(A, ((int)p+eps)/q) == K) {
                ansp = (int) p;
                ansq = q;
                break;
            }
            st.insert(q);
        }
        vector<int> ret = {ansp, ansq};
        return ret;
    }
};