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

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

那么第 k 个最小的分数是多少呢? 以整数数组的形式返回你的答案
标签：二分法
示例:
输入: 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]

分析图解来自B站花花酱，将队列转换成矩阵排列进行参考
特性：

• 每一行从左到右依次递减
• 每一列从下往上依次递减
• 每一行的数从左到右依次递减，第一次出现A[i]/A[j]<mid则后面的数均会小于mid

解题思路：

• 通过二分法确定第K小的分数所在范围 [l,r](实数二分）
  1、需要的变量 max-f（右边界的最大分数）total（A[i]/A[j]<mid分数个数）p, q（对应下标）
  2、确定A[i]/A[j]<mid个数 total，total数值更新

 while(j<n&& A[i]>mid*A[j]) j++;
 total+=(n-j);//每一行后面小于mid的个数累加
 if(n==j) break;//每行列举完成

如果 total >K, Kth在mid左边 r=mid，否则 l=mid

3、确定Kth具体数值
思路：当确定Kth在[l,r]范围内，则Kth必定是靠近右边界的最大分数
通过1中total的枚举更新靠近r的最大分数值 max_f以及对应的下标

  const double f=static_cast<double>(A[i])/A[j];
                if(f>max_f){
                    p=i;
                    q=j;
                    max_f=f;
                }

具体代码如下：

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
        const int n=A.size();
        double l=0,r=1;
        while(r>l){
            double mid=(l+r)/2;
            int p=0,q=0;
            int total=0;
            double max_f=0;
            int j=1;
            for(int i=0;i<n-1;i++){
                while(j<n&& A[i]>mid*A[j]) j++;//每一行的数从左到右依次递减，第一次出现A[i]/A[j]<mid则后面的数均会小于mid
                //两重循环
                total+=(n-j);//每一行后面小于mid的个数累加
                if(n==j) break;//每行列举完成
                const double f=static_cast<double>(A[i])/A[j];//static_cast是一个强制类型转换操作符。强制类型转换 强制f=A[i]/A[j];
                if(f>max_f){
                    p=i;
                    q=j;
                    max_f=f;
                }
            }
          if(total==K) 
                return {A[p],A[q]};
            else if(total>K)
                r=mid;
            else 
                l=mid;

        }
      return {};
    }
};