题目描述：

LeetCode 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]

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.

题目大意：

给定由1和素数组成的列表A（递增有序），求其中相互不同的元素两两相除的第K大的数对。

解题思路：

优先队列（Priority Queue）

首先将下标(0, 1), (0, 2) ... (0, N)加入优先队列pq，pq中的数对(i, j)按照A[i] / A[j]从小到大排序

执行K次如下操作：

从pq中弹出元素top，若top.x + 1 < top.y 则将top.x + 1, top.y加入pq

返回最后一次弹出的数对

Java代码：

public class Solution {

    public int[] kthSmallestPrimeFraction(int[] A, int K) {
        
        class Pair implements Comparable<Pair>{
            public int x;
            public int y;
            public Pair(int x, int y) {
                this.x = x;
                this.y = y;
            }
            public int compareTo(Pair p) {
                return A[x] * A[p.y] - A[y] * A[p.x];
            }
        }

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        for (int i = 1; i < A.length; i++) {
            pq.add(new Pair(0, i));
        }
        Pair top = null;
        for (int i = 0; i < K; i++) {
            top = pq.poll();
            if (top.x + 1 < top.y) {
                pq.add(new Pair(top.x + 1, top.y));
            }
        }
        return new int[]{A[top.x], A[top.y]};
    }

}

Python代码（Time Limit Exceeded）

class Solution(object):
    def kthSmallestPrimeFraction(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: List[int]
        """
        N = len(A)
        h = []
        for i in range(1, N):
            heapq.heappush(h, (float(A[0]) / A[i], 0, i))
        for x in range(K):
            v, p, q = heapq.heappop(h)
            if p + 1 < q:
                heapq.heappush(h, (float(A[p + 1]) / A[q], p + 1, q))
        return A[p], A[q]

 

本文链接：http://bookshadow.com/weblog/2018/02/18/leetcode-k-th-smallest-prime-fraction/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码