发表于 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 题目链接