786. K-th Smallest Prime Fraction

- 日理万妓 2023-06-03 15:55 12阅读 0赞

[https://www.cnblogs.com/grandyang/p/9135156.html][https_www.cnblogs.com_grandyang_p_9135156.html]

数组本身是排序的，所以固定一个数，从左向右得到的分数是逐渐减小的。

使用二分查找，设定一个值，然后统计所有小于这个数的个数，如果个数小于期望的k，那么把这个数调大再统计，如果大于期望k，把这个数调小再统计，直到个数等于k。

注意：1.left、right定义时必须是double的，因为分数不是整数

2.每次统计，统计的j的位置是第一个小于mid的位置，也就是说之前的数都是大于mid的，因为求的是第k小，所以必须是n-j来获得到底有多少个小的数

3.因为需要返回第k小的分数的分子、分母，所以必须进行保存。i固定j滑动每次停止的位置，肯定有一个是这个第k小的，但是你并不能保证i=0 j停止的数一定大于i = 1 j停止的数，所以取其中最大的就是真正的那个需要的数

4.mid\*A\[j\] < A\[i\] A\[i\]\*q > p\*A\[j\]都是为了保证除数进行无限循环

5.count < K的时候是left = mid，而不是right = mid，因为这个时候count不够，你需要调大mid值，调大也就是增大left

6.count的统计是i固定每个位置，然后j向后滑动得到的总的count值

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

转载于:https://www.cnblogs.com/ymjyqsx/p/11308933.html

[https_www.cnblogs.com_grandyang_p_9135156.html]: https://www.cnblogs.com/grandyang/p/9135156.html