既然来了，何不认真读完此文呢？每天多花20分钟，做一些别人不愿做的事，坚持下去，会有一个结果的。废话不多说，抓紧看文章，本文共包括如下知识：
- 学会列表和排序很难求解的场景
- 学会使用堆的场景
- 学会一个使用堆的案例
- 进一步提高对内置模块heapq的使用能力
1 超级抽数
题目来自 https://leetcode-cn.com/problems/super-ugly-number/，阿里面试曾考过此题，大家务必重视此题。
首先要理解题目，我做此题时，读题好几遍，才完全明白超级丑数的定义。
给定一个质数列表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).
今天就写到这里，如果对你有用，记得点赞鼓励哈 感谢！