曾经绊倒我的 “超级丑数”

既然来了，何不认真读完此文呢？每天多花20分钟，做一些别人不愿做的事，坚持下去，会有一个结果的。废话少说，通过此文，你将会学到如下知识：

1. 学会列表和排序很难求解的场景
2. 学会使用堆的场景
3. 学会一个使用堆的案例
4. 进一步提高对内置模块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).