欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-14 22:55:34
...

题目描述
一个已排序好的表 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;
                }

LeetCode 786. 第 K 个最小的素数分数
具体代码如下:

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 {};
    }
};
相关标签: 二分法