直接抄星主的：

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

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

示例:

# 输入: 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] 。
# 说明:

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

    # 来源：力扣（LeetCode）
    # 链接：https://leetcode-cn.com/problems/super-ugly-number
    # 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

超级丑数题目来源：

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

首先理解题目，我做此题，读题好几遍，才完全明白超级丑数的定义。给定一个质数列表primes，如果一个数的所有质数列表是primes的子集，则这个数为超级丑数。

题目要求，在给定primes情况下，求出第n个丑数。

分析过程

先从暴力枚举开始分析，假定primes等于[2,5,13]，依次列举出所有肯能的丑数：1, 2, 4, 8,

16, 32, ….

糟糕！因为光使用一个素数2，就能列举出很多。幸好此题限定一个丑数的上限，在32

位有符整数范围内(最大值为：2的31次方减1)，即便如此穷举的情况还是很多。

此题不太容易确定所有的丑数序列，完整的序列无法确定，排序也就无从谈起，因此通过从小到大排序后找出第n个丑数的方法就不可行。

对于无法提前预知整个列表，或者构建出整个序列耗费时间或占用内存过大时，可以考虑使用堆，对应Python中的

heapq 模块。

这道题使用heapq的求解思路如下：

1) 构建heapq，装入第一个元素，即素数1；

2

移出heapq的根元素ugly，遍历primes拿出prime，同时与prime的元素相乘，得到一个新的丑数，并装入到heapq中。备注：Python中heapq是一个小根堆，也叫做优先级队列，在装入heapq中时，对象内部总会维护一个小根堆，所以每次pop时，都是当前heapq的最小值。

3

利用上述特性，当移出n个元素时，实际上相当于从已排序好的列表中找到其第n个小的元素，这不就是丑数列表排序好后，第n个丑数吗！真是返回的结果。

需要注意，丑数装入heapq时，不要出现重复。解决起来也很方便，使用集合set防止重复添加。

class Solution:
    def nthSuperUglyNumber(self, n, primes):
        import heapq
        nums,ugly = [],0
        s = set()
        heapq.heapify(nums)
        heapq.heappush(nums,1)
        for _ in range(n):
            ugly = heapq.heappop(nums)
            for i in primes:
                temp = ugly * i
                if temp not in s:
                    s.add(temp)
                    heapq.heappush(nums,temp)
                    print(nums)
        return ugly


def test_nthSuperUglyNumber():
    s = Solution()
    assert s.nthSuperUglyNumber(12, [2,7,13,19]) == 32