786. 第 K 个最小的素数分数

素颜马尾好姑娘i 2023-02-26 07:21 6阅读 0赞

一个已排序好的表 A，其包含 1 和其他一些素数. 当列表中的每一个 p<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

来源：力扣（LeetCode）  
链接：[添加链接描述][Link 1]

二分法：  
先找出恰好大于k个组合的分数的一个值。  
再找出最接近这个值的分数组合。

class Solution {
        
    public:
        int small_than_D(vector<int>& A, double d){
        
            int res = 0;
            for(int i = 0; i < A.size(); i++){
        
                res += A.end() - upper_bound(A.begin()+i+1, A.end(), A[i]/d);
                //d = 1/2， A[0] = 1，比2大的数和1组合都比d小
            }
            return res;
        } 
    
        vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
        
            double l = 0;
            double r = 1;
    
            double mid;
            while(l < r) {
        
                mid = l + (r - l)/2;
                int count = small_than_D(A, mid);
                if(count == K) {
        
                    l =  mid;
                    r = mid;
                    break;
                }else if(count > K) {
        
                    r = mid;
                }else {
        
                    l = mid;
                }
            }
    
            int p = 1;
            int q = A.back();
            for(int i = 0; i < A.size(); i++){
        
                int tp = A[i];
                auto it = upper_bound(A.begin()+i+1, A.end(), A[i]/l);
                if(it != A.end()){
        
                    int tq = *it;
                    if( l - 1.0*tp/tq < l - 1.0*p/q){
        
                    p = tp;
                    q = tq;
                }
                }
            }
            vector<int> ans;
            ans.push_back(p);
            ans.push_back(q);
            return ans;
        }
    };

[Link 1]: https://leetcode-cn.com/problems/k-th-smallest-prime-fraction