题目描述

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

那么第 K 个最小的分数是多少呢？以整数数组的形式返回你的答案，这里 answer[0] = p 且 answer[1] = q。

样例

输入：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]

提示

• A 的取值范围在 2 到 2000。
• 每个 A[i] 的值在 1 到 30000。
• K 取值范围为 1 到 A.length * (A.length - 1) / 2。

算法1

(堆，贪心) $O(K \log n)$

1. 经过试验，直接构造所有的分数然后排序的暴力做法会超时。
2. 我们可以利用贪心巧妙的构造，我们首先令 A[0] / A[1], A[0] / A[2], ..., A[0] / A[n - 1] 插入到小根堆，因为这是最小的 n 个数。
3. 然后我们每次从小根堆中弹出最小的分数，假设弹出的分数为 A[i] / A[j]，如果这不是第 K 次弹出且 i + 1 < j，则我们将 A[i + 1] / A[j] 插入到小根堆中，因为这是以 A[j] 为分母时，目前最小的一个分数。
4. 如此弹出 K 次，第 K 次弹出的分数一定是第 K 小的分数。

时间复杂度

• 堆中至多有 $n$ 个元素，操作一次的时间复杂度为 $O(\log n)$，共操作 $K$ 次，故时间复杂度为 $O(K \log n)$。
• 这个算法已经超时了。

空间复杂度

• 存放堆需要 $O(n)$ 的空间。

C++ 代码

class MyPair {
public:
    int x, y;
    int first, second;

    MyPair(int x_, int y_, int first_, int second_): 
        x(x_), y(y_), first(first_), second(second_) {}

    bool operator < (const MyPair &other) const {
        return x * other.y > y * other.x;
    }
};


class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
        int n = A.size();

        priority_queue<MyPair> q;

        for (int i = 1; i < n; i++)
            q.push(MyPair(A[0], A[i], 0, i));

        while (K--) {
            auto tp = q.top();
            if (K == 0) 
                return {q.top().x, q.top().y};

            q.pop();
            if (tp.first + 1 == tp.second)
                continue;
            q.push(MyPair(A[tp.first + 1], A[tp.second], tp.first + 1, tp.second));
        }

        return {-1, -1};
    }
};

算法2

(二分答案，双指针) $O(n \log 10^8)$

1. 二分答案的上下界设为 $(0, 1)$。精度假设为 $10^{-8}$。
2. 给定一个实数 $m$，可以通过双指针的算法计算出严格小于 $m$ 的组合数量。
   • 对于每个 $i$，找到最大的 $j$，满足 A[i] / A[j] < m。注意到 $j$ 是随着 $i$ 单调不减的。
3. 最后找到目标的实数，再用一次双指针找到等于它的实数即可（由于数字都是质数，所以答案唯一）。

时间复杂度

• 二分的次数为 $O(\log 10^8)$。
• 每次二分判定，双指针的时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n \log 10^8)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

#define eps 1e-8

class Solution {
private:
    int count(const vector<int> &A, double m) {
        const int n = A.size();
        int tot = 0;
        for (int i = 1, j = 0; i < n; i++) {
            while (1.0 * A[j] / A[i] - m < -eps) j++;
            tot += j;
        }
        return tot;
    }

public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
        double l = 0, r = 1;
        while (fabs(l - r) > eps) {
            double mid = (l + r) / 2;
            if (count(A, mid) < K) l = mid;
            else r = mid;
        }

        const int n = A.size();
        for (int i = 1, j = 0; i < n; i++) {
            while (1.0 * A[j] / A[i] - l < -eps) j++;

            if (fabs(1.0 * A[j] / A[i] - l) <= eps)
                return {A[j], A[i]};
        }

        return {0, 0};
    }
};