题目描述

A sorted list A contains 1, plus some number of primes. Then, for every p < q in the list, we consider the fraction p/q.

What is the K-th smallest fraction considered? Return your answer as an array of ints, where answer[0] = p and answer[1] = q.

Examples:
Input: A = [1, 2, 3, 5], K = 3
Output: [2, 5]
Explanation:
The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3.
The third fraction is 2/5.

Note:

• A will have length between 2 and 2000.
• Each A[i] will be between 1 and 30000.
• K will be between 1 and A.length * (A.length - 1) / 2.

题意：给一个由1和若干个素数组成的数组，求数组中第$k$小的真分数。

算法1

(优先队列）

题解1：一般第$K$小的数都可以使用优先队列来解。我们首先维持一个$n-1$个元素小顶堆优先队列，分别代表分子为1，分母分别为后面$n-1$个质数组成的分数，那么最小值肯定这其中一个元素。假设我们将最小的元素$A[j]/A[i]$出队列后，添加一个$A[j+1]/A[i]$的分数，那么下一个最小值肯定在仍然在这个队列中。重复上述操作，直至$k$个元素出队列。时间复杂度$O(Klogn)$

其实相当于维护了K个指针，只是使用优先队列来维护最小值。

1/2 
1/3 2/3
1/5 2/5 3/5
1/7 2/7 3/7 5/7
先将1/2，1/3，1/5，1/7入队列，1/7为最小，出队列，将2/7进入队列。此时下一个最小值肯定在[1/2,1/3,1/5,2/7]   中，此时1/5是最小的，那么将1/5出队列，2/5进入队列，下一个最小值肯定在[1/2,1/3,2/5,2/7]中。

C++ 代码

    struct Fraction{
        int x,y,index;//分子，分母，分子在数组中的下标
        Fraction(int x,int y,int index):x(x),y(y),index(index){}
        bool operator< (const Fraction &b) const
        {       //c++   默认是大顶堆，所以需要运算符重载
            return x * b.y > y * b.x;
        }
    };
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
        priority_queue<Fraction> q;
        int n = A.size();
        for(int i = 1 ; i < n ; i ++)
            q.push(Fraction(1,A[i],0));//先将所有分母为1的分数入队列
        while(K > 1)//
        {
            Fraction p = q.top();
            q.pop();
            if(p.index + 1 < n)//分母不变，分子变为之前分子在数组中的下一个元素
                q.push(Fraction(A[p.index + 1],p.y,p.index + 1));
            K -- ;
        }
        Fraction p = q.top();
        return vector<int>{p.x,p.y};
    }

算法2

(二分搜索)

对于第$K$小的题目有时候也可以使用二分来做，最后的解肯定在$[0,1]$之间，统计小于target的数有多少个。如果小于target的数少于K个，说明答案应该比target大，否则答案应该比target小。这题的麻烦之处在于，不是整数上的二分，而最终的结果还是两个整数的比值。

C++ 代码

    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
        int n = A.size();
        double left = 0.0 ,right = 1.0;
        int count = 0;
        int p = 0, q = 0;
        while(true)
        {
            double mid = (left + right) / 2;
            count = 0;
            double eps = 1.0;
            for(int i = 1 ; i < n ; i ++)
            {   int j = 0;
                for(; j < i ; j ++)
                {       
                    //统计小于等于mid的数的count
                    if((double)A[j] / (double)A[i] <= mid)
                        count ++;
                    else
                        break;
                }
                    //j代表的是第一个大于mid的A[j]/A[i]，所以小于等于mid的是前面的一个元素。
                //求解最接近mid的真分数。
                if(j > 0){
                    double cur_eps = mid - (double)A[j - 1]/A[i];
                    if(cur_eps > 0 && cur_eps < eps)
                        p = j - 1,q = i,eps = cur_eps;
                }      
            }
            if(count < K)
                left = mid;
            else if(count > K)
                right = mid;
            else{
                return vector<int>{A[p],A[q]};
            }
        }
        return vector<int>{A[p],A[q]};
    }