JZX轻语：简

LeetCode 786 - 第K个最小的质数分数

发表于2024年05月06日

#堆

一般求解第k小的问题都可考虑使用堆来解决，首先最小的分数为最小的质数/最大的质数，先将它加入到堆中。每次从堆中处理当前最小的分数时，将其分母左移一位or分子右移一位，再将这两个数放在堆中。直至处理第k个数即可。由于期间可能会有重复的添加，因此需要引入一个记录上次处理的分子/分母数据，以去重。

import heapq


class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        pq = [(arr[0] / arr[-1], 0, len(arr) - 1)]

        i = 0
        last_l, last_r = -1, -1
        while True:
            div, l, r = heapq.heappop(pq)
            # 去重
            if last_l == l and last_r == r:
                continue
            last_l, last_r = l, r
            i += 1
            if i == k:
                return [arr[l], arr[r]]
            if l + 1 < r:
                heapq.heappush(pq, (arr[l + 1] / arr[r], l + 1, r))
                heapq.heappush(pq, (arr[l] / arr[r - 1], l, r - 1))

闪念标签：LC

题目链接：https://leetcode.cn/problems/k-th-smallest-prime-fraction/