313_超级丑数

类型：堆

• 313. 超级丑数 💛

  https://leetcode-cn.com/problems/super-ugly-number/

  ❓ 给你一个长度为 k 的质数列表 primes，如果某个数因式分解后，其所有质因数都在 primes 内，那么这样的数被称为超级丑数。请你返回从小到达排序的第 n 个超级丑数。

  输入: n = 12, primes = [2,7,13,19] 输出: 32 解释: 前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

  💡 堆

  一个丑数由 primes 中的质因子相乘得来。那么根据因式分解的性质，一个丑数与 primes 中的数字相乘，得到的也是丑数。这样我们就知道了如何构建出一个丑数来。题目要求我们返回升序排列的第 n 个丑数。因此我们需要用一个小顶堆来实现。

  class Solution:
      def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
          heap = [1]
          ans = None
          lastNum = None
          for _ in range(n):
              while True:
                  lastNum = ans
                  ans = heapq.heappop(heap)
                  if lastNum != ans:
                      break
              for prime in primes:
                  newPrime = ans * prime
                  heapq.heappush(heap, newPrime)
                  lastNum = newPrime
          return ans