Formatted question description: https://leetcode.ca/all/786.html

786. K-th Smallest Prime Fraction

Level

Hard

Description

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:

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

Solution

Use a priority queue to store the fractions, where the smallest fraction is polled first. Initially, offer all [A[0], A[i]] where 0 < i < A.length to the priority queue. Since A[0] is 1 and the smallest fraction has a numerator 1, the smallest fraction is in the priority queue.

Then poll the smallest fraction from the priority queue for K - 1 times. To ensure that the remaining smallest fraction is in the priority queue, each time a fraction is polled, try to find the next smallest fraction and offer it to the priority queue if it exists. Suppose the fraction polled is [A[i], A[j]] where 0 <= i < j < A.length. If i + 1 < j, then offer the new fraction [A[i + 1], A[j]] to the priority queue.

After the K - 1 times, the next element to be polled from the priority queue is the K-th smallest prime fraction, so return the fraction.

  • class Solution {
        public int[] kthSmallestPrimeFraction(int[] A, int K) {
            Map<Integer, Integer> numIndexMap = new HashMap<Integer, Integer>();
            int length = A.length;
            for (int i = 0; i < length; i++)
                numIndexMap.put(A[i], i);
            PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
                public int compare(int[] fraction1, int[] fraction2) {
                    return fraction1[0] * fraction2[1] - fraction2[0] * fraction1[1];
                }
            });
            for (int i = 1; i < length; i++) {
                int[] fraction = {A[0], A[i]};
                priorityQueue.add(fraction);
            }
            for (int i = 1; i < K; i++) {
                int[] fraction = priorityQueue.poll();
                int numeratorIndex = numIndexMap.get(fraction[0]), denominatorIndex = numIndexMap.get(fraction[1]);
                if (numeratorIndex + 1 < denominatorIndex) {
                    numeratorIndex++;
                    int[] newFraction = {A[numeratorIndex], fraction[1]};
                    priorityQueue.offer(newFraction);
                }
            }
            return priorityQueue.peek();
        }
    }
    
  • // OJ: https://leetcode.com/problems/k-th-smallest-prime-fraction/
    // Time: O(KlogN)
    // Space: O(N)
    class Solution {
        typedef array<int, 2> T;
    public:
        vector<int> kthSmallestPrimeFraction(vector<int>& A, int k) {
            auto cmp = [&](T &a, T &b) { return (double)A[a[0]] / A[a[1]] > (double)A[b[0]] / A[b[1]]; };
            priority_queue<T, vector<T>, decltype(cmp)> pq(cmp);
            for (int i = 0; i < A.size() - 1; ++i) pq.push({ i, (int)A.size() - 1 });
            while (--k) {
                auto [a, b]  = pq.top();
                pq.pop();
                if (a != b - 1) pq.push({ a, b - 1 });
            }
            auto [a, b] = pq.top();
            return { A[a], A[b] };
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions