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 arduino控制ps2手柄一直报错
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥85 maple软件,solve求反函数,出现rootof怎么办?
  • ¥15 求chat4.0解答一道线性规划题,用lingo编程运行,第一问要求写出数学模型和lingo语言编程模型,第二问第三问解答就行,我的ddl要到了谁来求了
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿