weixin_47261246 2020-06-26 18:32 采纳率: 12.5%
浏览 176
已结题

有序列表A包含1和一些素数。那么,对于列表中的每一项p< q,第k小的分数p/q是多少?以整数数组的形式返回答案,其中answer[0] = p和answer[1] = q。并算法的时间复杂度小于O(N^2)

问题简介:有序列表A包含1和一些素数。那么,对于列表中的每一项p< q,第k小的分数p/q是多少?以整数数组的形式返回答案,其中answer[0] = p和answer[1] = q。并算法的时间复杂度小于O(N^2)

要求:
(a)设计一个时间复杂度优于O(n^2)的算法,其中n是数组a的大小,这意味着不列出所有的分数,代价为O(n^2)。对算法进行了分析,并使用顺序表示法给出了结果。
(b)在Python中以函数的形式实现算法:
def kth_smallest_fraction (A, k):

图片说明

  • 写回答

1条回答 默认 最新

  • threenewbee 2020-06-26 23:55
    关注
    #include<iostream>
    #include<vector>
    using namespace std;
    class Solution{            //二分查找       
    public:
        vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) 
        {
            double left = 0, right = 1.0, mid;
            int p = 0;
            int q = 1;
            int Asize = A.size();
            int count; 
            while (true) 
            {
                double mid = (left + right) / 2.0;
                count = 0; 
                p = 0;
                for (int i = 0, j = i+1; i < Asize; ++i) 
                {
                    while (j < Asize && mid < (double)A[i]/(double)A[j]  )
                    {
                        ++j;
                    }
                    count += Asize - j;     //记录在 mid 之前数的个数
                    if (j < Asize && (double)p/(double)q < (double)A[i]/(double)A[j])   //记录此时在mid之前的最大的 p / q
                    {
                        p = A[i];
                        q = A[j];
                    }
                }
                if (count == K)         //若相等就返回此时的p q
                {
                    return {p, q};
                }
                else if (count < K)     //若 count < K 就缩小区间为[mid,right]
                {
                    left = mid;
                }
                else                    //若 count > K 就缩小区间为[left,mid]
                {
                    right = mid;
                }
            }
        }
    };
    
    
    评论

报告相同问题?

悬赏问题

  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀
  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组