Java实现 LeetCode 786 第 K 个最小的素数分数(大小堆)

flowchart 箭头图标 勿删

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

一个已排序好的表 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

PS：

因为求出来的都是小于1的，我们直接按照值得范围去查找

大小堆主要是分堆得时候不好分

class Solution {

  public int[] kthSmallestPrimeFraction(int[] A, int K) {

        if (null == A || A.length <= 0) return A;

        double lo = 0, hi = 1;

        int[] ans = new int[2];

        while (lo <= hi) {

            double mid = lo + (hi - lo) / 2;

            int[] finds = findKthFraction(A, mid);

            if (finds[0] < K)

                lo = mid;

            else if (finds[0] > K)

                hi = mid;

            else {

                ans[0] = finds[1];

                ans[1] = finds[2];

                return ans;

            }

        }

        return ans;

    }

    private int[] findKthFraction(int[] fraction, double x) {

        int p = 0, q = 1, count = 0, i = -1; //p 分子  q 分母

        for (int j = 1; j < fraction.length; ++j) {

            //这里的筛选是，按照指定的值的范围去寻找，本来是fra[i+1]/fra[j]<x

            while (i < fraction.length && fraction[i + 1] < fraction[j] * x) ++i;

            count += i + 1;

            //  A / B - C / D = A * D / B * D - C * B / B * D;

            //=> A * D - B * C

            if (i >= 0 && p * fraction[j] < q * fraction[i]) {

                p = fraction[i];

                q = fraction[j];

            }

        }

        return new int[]{count, p, q};

    }

}