786. K-th Smallest Prime Fraction

Question:

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]

Note:

  1. A will have length between 2 and 2000.
  2. Each A[i] will be between 1 and 30000.
  3. K will be between 1 and A.length * (A.length - 1) / 2.

Solution:

  • Method 1: PriorityQueue TLE 
      class Solution {
      public int[] kthSmallestPrimeFraction(int[] A, int K) {
          PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
              @Override
              public int compare(int[] a, int[] b){
                  double ratioA = a[0] * 1D / a[1];
                  double ratioB = b[0] * 1D / b[1];
                  if(ratioA < ratioB) return -1;
                  else if(ratioA > ratioB) return 1;
                  return 0;
              }
          });
          int n = A.length;
          for(int i = 0; i < n; i++){
              for(int j = i + 1; j < n; j++){
                  pq.offer(new int[]{A[i], A[j]});
              }
          }
          int i = 1;
          while(i++ < K) pq.poll();
          return pq.peek();
      }
  }
  • Method 2: Binary Search Imgur 
      class Solution {
      public int[] kthSmallestPrimeFraction(int[] A, int K) {
          int n = A.length;
          double left = 0D, right = 1D;
          while(left < right){
              double mid = left + (right - left) / 2;
              double max_f = 0D;
              int total = 0;
              int p = 0, q = 0;
              for(int i = 0, j = 1; i < n - 1; i++){
                  while(j < n && A[i] > mid * A[j]) ++j;
                  if(n == j) break;
                  total += (n - j);
                  double cur = A[i] * 1D / A[j];
                  if(cur > max_f){
                      p = i;
                      q = j;
                      max_f = cur;
                  }
              }
              if(total == K) return new int[]{A[p], A[q]};
              else if(total > K) right = mid;
              else left = mid;
          }
          return new int[]{};
      }
  }

Reference

  1. 花花酱 LeetCode 786. K-th Smallest Prime Fraction