leetcode786

786. K-th Smallest Prime Fraction

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.

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

Idea

Binary Search + Matrix
cited from 花花酱

Code

class Solution(object):
    def kthSmallestPrimeFraction(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: List[int]
        """
        l = 0.0
        r = 1.0
        n = len(A)
        while l < r:
            m = l + (r - l) / 2
            max_f = 0.0
            tot = 0
            p, q = 0, 0
            j = 1
            for i in range(0, n - 1):
                while j < n and A[i] > m * A[j]: # find the first ele in a row smaller than m
                    j += 1
                tot += n - j # add the number of elements smaller than m in this row
                if n == j: # no ele smaller than m
                    break
                f = 1.0 * A[i] / A[j]
                if f > max_f: # find the largest frac in the k fracs
                    p, q, max_f = i, j , f
            if tot == K:
                return [A[p], A[q]]
            elif tot > K: # m too large
                r = m
            else:         # m too small
                l = m
        return []