313.超级丑数.md

313.超级丑数

https://leetcode-cn.com/problems/super-ugly-number/solution/313chao-ji-chou-shu-dui-pai-xu-si-lu-jia-v4iv/

难度：中等

题目：

编写一段程序来查找第 n 个超级丑数。

超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

说明:

• 1 是任何给定 primes 的超级丑数。
• 给定 primes 中的数字以升序排列。
• 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
• 第 n 个超级丑数确保在 32 位有符整数范围内。

示例：

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

分析

我们可以动态维护一个当前最小的超级丑数。找到第一个，我们将其移除，再找下一个当前最小的超级丑数。 这样经过 n 轮，我们就得到了第 n 小的超级丑数。这种动态求极值的方式，符合堆排序的操作条件。

1. 初始化ret = 1 为默认的返回值
2. 我们通过for循环的方式每次找到一个最小值，默认为1。
3. 最小值tmp出堆时，分别和primes中的每次元素p相乘后入堆。
4. 此时，我们将tmp赋值给ret
5. 如此反复3、4操作，直到取到第 n 个超级丑数。

在3 操作的时候，我们需要注意，由于在计算时可能存在相同值的场景，所以在出堆后，需要判断当前堆的最小值是否等于tmp， 如果等于，则需要持续出堆，一直到不相等为止。

解题：

import heapq

class Solution:
    def nthSuperUglyNumber(self, n, primes):
        hq = [1]
        ret = 1
        for i in range(n):
            tmp = heapq.heappop(hq)
            while hq and hq[0] == tmp:
                heapq.heappop(hq)
            for p in primes:
                heapq.heappush(hq, p * tmp)
            ret = tmp
        return ret

欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

有喜欢力扣刷题的小伙伴可以加我微信（King_Uranus）互相鼓励，共同进步，一起玩转超级码力！

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown