既然来了，何不认真读完此文呢？每天多花20分钟，做一些别人不愿做的事，坚持下去，会有一个结果的。废话不多说，抓紧看文章，本文共包括如下知识：
学会列表和排序很难求解的场景学会使用堆的场景学会一个使用堆的案例进一步提高对内置模块heapq的使用能力1 超级抽数
阿里面试曾考过此题，大家务必重视此题。
首先要理解题目，我做此题时，读题好几遍，才完全明白超级丑数的定义。
给定一个质数列表primes，如果一个数的所有质数构成的列表是primes的子集，则此数为超级丑数。
因此，超级抽数依赖于给定的primes，要求求出第n个丑数。
示例
输入: 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] 。
列表和排序很难求解
先从暴力枚举开始分析，假定primes等于[2,5,13]，依次列举出所有可能的丑数：1, 2, 4, 8, 16, 32, …. 糟糕！因为仅仅使用一个素数2，就能列举出很多。幸好此题限定一个丑数的上限，在32位有符整数范围内(最大值为：)，即便如此,穷举的情况依然非常复杂，更别提求解第n个丑数了！
的确，此题不太容易确定所有的丑数序列，完整的序列无法确定，买二手平台排序也就无从谈起。因此，通过从小到大排序后找出第n个丑数的方法就不可行。
经验：对于无法提前预知整个列表，或者构建出整个序列耗费时间较长，或占用内存过大时，求第n个丑数，往往不太适合使用列表！
使用堆的场景
考虑使用堆，对应Python中heapq模块，它专治以上三种情况发生时，求解第n个丑数。
这道题使用heapq的求解思路如下：
step1 构建heapq，装入第一个元素，即素数1；step2 移出heapq的根元素ugly，遍历primes拿出prime，同时与prime的元素相乘，得到一个新的丑数，并装入到heapq中。备注：Python中heapq是一个小根堆，也叫做优先级队列，在装入heapq中时，对象内部总会维护一个小根堆，所以每次pop时，都是当前heapq的最小值。step3 利用上述特性，当移出n个元素时，实际上相当于从已排序好的列表中找到其第n个小的元素，这不就是丑数列表排序好后，第n个丑数吗！正是想要的结果第n个丑数。
需要注意，丑数装入heapq时，不能出现重复。解决起来也很方便，使用集合set防止重复添加。
代码
将上述思路兑现为代码：
class Solution(object):
def nthSuperUglyNumber(self, n, primes):
"""
:type n: int
:type primes: List[int]
:rtype: int
"""
nums, i, s = [], 0, set()
heapify(nums)
heappush(nums, 1) # step1
ugly = 0
for _ in range(n): # step2
ugly = heappop(nums)
for prime in primes:
uglyCombine = ugly * prime
if uglyCombine not in s: # step3
s.add(uglyCombine)
heappush(nums, uglyCombine)
return ugly
时间复杂度等于 O(knlogn)，k为primes长度，n为第几个丑数; 空间复杂度为O(n).
今天就写到这里，如果对你有用，记得点赞鼓励哈 感谢！
