786 K-th Smallest Prime Fraction

786. K-th Smallest Prime Fraction

1. Question

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

What is theK-th smallest fraction considered? Return your answer as an array of ints, whereanswer[0] = pandanswer[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.

Input: A = [1, 7], K = 1
Output: [1, 7]

Note:

• Awill have length between2and2000.

• EachA[i]will be between1ande30000.

• Kwill be between1andA.length * (A.length - 1) / 2.

2. Implementation

(1) Binary Search

思路: 和lc378, LC 668, lc719类似，可以用二分法找到第K个最小Prime Fraction

• 首先要用二分法，我们要先确定初始的搜索的范围，由于要找的是fraction，所以我们先从[0, 1]这个范围开始搜索。但要注意的是，我们不能用start + 1 < end这样的方式写二分法的模板，因为我们要找的数不是一个整数，而是一个double。

• 每次二分法，我们先找到一个target的fraction(代码里的mid)，然后我们找出有多少个fraction是小于等于这个fraction。如果小于等于target fraction的次数小于K, 说明target fraction太小，将搜索范围缩小到[mid, end]，否则target的次数大于K, target fraction太大， 将范围缩小到[start, mid]

• 由于我们要范围第K个最小fraction是的分子和分母，所以每次在找小于等于target fraction的个数的同时，我们也在记录小于target fraction的最大的fraction的分子和分母。

• 在计算小于等于target fraction的过程中，我们用了two pointer的方法，实现只用O(n)的时间找到，具体的做法其实是用一个virtual matrix，具体解法参考 https://www.youtube.com/watch?v=ZzfXmZgJ0cw

class Solution {
    public int[] kthSmallestPrimeFraction(int[] A, int K) {
        double start = 0, end = 1;
        int numerator = 0, denominator = 1;
        int n = A.length;

        while (start < end) {
            double mid = start + (end - start) / 2;

            int count = 0;
            double maxFraction = 0;
            int j = 1;

            for (int i = 0; i < n - 1; i++) {
                while (j < n && A[i] > A[j] * mid) ++j;

                count += (n - j);

                if (j == n) break;

                double curFraction = (double)A[i]/A[j];
                if (curFraction > maxFraction) {
                    numerator = A[i];
                    denominator = A[j];
                    maxFraction = curFraction;
                }
            }

            if (count == K) {
                return new int[] {numerator, denominator};
            }
            else if (count < K) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        return new int[0];
    }
}

3. Time & Space Complexity

Binary Search: 时间复杂度O(n * log(MAX)), max是搜索的范围，即[0, 1]的所有double值，n是输入数组A的长度。空间复杂度O(1)