786. 第 K 个最小的素数分数

Difficulty
Hard
Tags
堆
URL
https://leetcode-cn.com/problems/k-th-smallest-prime-fraction/
Star
给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数 组成，且其中所有整数互不相同。
对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。
那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。
示例 1：
输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5
示例 2：
输入：arr = [1,7], k = 1
输出：[1,7]
提示：
  • 2 <= arr.length <= 1000
  • 1 <= arr[i] <= 3 * 104
  • arr[0] == 1
  • arr[i] 是一个 素数 ，i > 0
  • arr 中的所有数字 互不相同 ，且按 严格递增 排序
  • 1 <= k <= arr.length * (arr.length - 1) / 2
通过次数26,798提交次数39,538

小顶堆

思路
暴力遍历所有的 分数，然后用小根堆来维护，这样空间复杂度为O(k)。
当堆中元素不够 k 个 或者 当前分数大于堆顶时，才放入堆中，因为只有这两种情况下，当前分数才可能是最终的结果。
题解
class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        h = []
        for i in range(0, len(arr)):
            for j in range(i+1, len(arr)):
                val = arr[j] / arr[i]
                if len(h) < k or h[0][0] < val:
                    heapq.heappush(h, [val, arr[i], arr[j]])
                
                if len(h) > k:
                    heapq.heappop(h)
                
        return h[0][1:]