【二分难题】力扣786-第K个最小的素数分数

摘要: 力扣 786，二分的经典题，外层值域二分，内层区间二分。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

今天我们来看一个二分的问题，在文章 二分 中，我们系统梳理过力扣上的二分的题目，可以看到变化还是很多的。

本题是其中的一个经典问题，它的答案需要通过值域二分来找到。我们知道二分中有一个判定条件，本题中的判定条件又需要二分来解决。因此本题相当于是二分里面又套了一个二分，把本题搞明白非常有助于加深对二分的理解。

---

$1 题目

题目链接

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

题目描述

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

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

注意:

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

样例

示例:
输入: 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]

$2 题解

算法: 二分 + 二分

值域二分：直接找第 k 大的分数是很难的，但是给定一个数，回答【小于等于该数的分数有多少个】这个问题是简单的。因此外层用值域二分找一个分数，该分数满足”小于等于该数的 fraction 有 K 个”。

给定分数 mid 之后，我们要回答 “小于等于 mid 的分数有多少个” 这个问题。

这个问题最简单的方式是先从 0 到 n - 2 枚举 i，A[i] 作为 p，然后从 i + 1 到 n - 1 枚举 j，A[j] 作为 q，这样就枚举了所有满足 p < q 的分数 p/q。之后判断 p/q 与 mid 的关系进行处理即可，代码如下：

int cnt = 0, p = -1, q = -1;
int n = A.size();
double maxx = 0;
for(int i = 0; i <  n - 1; ++i)
{
    for(int j = i + 1; j < n; ++j)
    {
        double frac = double(A[i]) / A[j];
        if(frac <= mid)
        {
            ++cnt;
            if(frac > maxx)
            {
                maxx = frac;
                p = A[i];
                q = A[j];
            }
        }
    }
}

以上面的枚举方式为基础，可以做以下优化。思路就是对于每一行，找到满足条件的下标，然后通过下标直接计算这一行中“小于等于某个数”的个数。具体如下：

假设 p = A[i] 已经确定了，我们要在 A[i+1..n-1] 中找到满足 p/q <= mid 的 q，也就是满足 q >= p/mid。

因为 A 是单调递增的，如果我们找到了某个 A[idx]，满足 A[idx] >= p/mid，那么对于 idx + 1 <= j <= n - 1，当然也满足 A[j] >= p/mid。

因此如果我们在 A[i+1..n-1] 中找到了满足大于等于 p/mid 的最小的值为 A[idx]，则 p = A[i] 对应的满足大于等于 p/mid 的 q 的个数为 n - idx。

在 A[i+1..n-1] 中寻找满足大于等于 p/mid 的最小的值为 A[idx]，这一步可以用二分的方式做。

在这个过程中每次二分时也求出对应的 p 和 q，用于记录答案。用结构体维护 check 函数返回的数据。cnt 为小于等于 p/q 的个数。

struct Fraction
{
    int p, q, cnt;
    Fraction(int p, int q, int cnt):p(p),q(q),cnt(cnt){}
};

代码(C++)

主体的二分：算法主体通过二分找到一个数，这个数是满足"小于等于该数的fraction有K个"的最小的数
二分的 check 条件： 对于 mid，统计小于等于 mid 的 fraction 个数
"统计小于等于某个数"也用二分来实现

struct Fraction
{
    int p, q, cnt;
    Fraction(int p, int q, int cnt):p(p),q(q),cnt(cnt){}
};

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
        int n = A.size();
        double left = (double)A[0] / A[n - 1];
        double right = 1.0;
        vector<int> result(2, -1);
        while(left < right)
        {
            double mid = (right + left) / 2;
            Fraction fraction = _leq(A, mid); // 小于等于 mid 的分数 p / q 的个数，同时记录最大的 p / q
            result[0] = fraction.p;
            result[1] = fraction.q;
            if(fraction.cnt > K)
                right = mid;
            else if(fraction.cnt < K)
                left = mid;
            else
                break;
        }
        return result;
    }

private:
    Fraction _leq(const vector<int>& A, double mid)
    {
        // 小于等于 mid 的 fraction 有几个
        int cnt = 0, p = -1, q = -1;
        int n = A.size();
        double maxx = 0;
        for(int i = 0; i < n - 1; ++i)
        {
            // p = (double)A[i];
            // A[i+1..n-1] 中寻找满足大于等于 p/mid 的最小的值为 A[idx]
            int left = i + 1, right = n - 1;
            while(left < right)
            {
                int mmid = (left + right) / 2;
                if((double)A[i] / mid > A[mmid])
                    left = mmid + 1;
                else
                    right = mmid;
            }
            int idx = left;
            // 边界情况的判定
            if((double)A[i] / mid > A[idx])
                continue;
            cnt += n - idx;
            double frac = (double)A[i] / A[idx];
            if(frac > maxx)
            {
                maxx = frac;
                p = A[i];
                q = A[idx];
            }
        }
        return Fraction(p, q, cnt);
    }
};

---