313.md

Super Ugly Number

Description

link

---

Solution : HEAP

核心思路在于如何找到下一个最小的丑陋数字加入数组中，故创建一个�heap，结构如下:

• value:是当前这个节点的数值，也是丑陋数字，但是不一定是最小的
• index:当前prime的第一个还未乘过的丑陋数字
• prime:当前prime

可以把每一个节点当作当前prime的序列，其中index意味着这个系列的下一个最小值是多少，因为当前dq里面保存了之前的每一轮prime系列当前的数字，所以只要存在其他系列的数字小于当前系列的下一轮数字，dq就会发生转换，保证了dq的最小值即为下一个丑陋数字的最小值

---

Code

Complexity T : O( log(k)N )

class Solution:
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        if not primes:
            return 0
        
        ugly_number = [1 for _ in range(n)]
        hq = [(prime, 1, prime) for prime in primes] # context (value, index, prime)
        heapq.heapify(hq)
        
        for i in range(1, n):
            ugly_number[i] = hq[0][0]
            while ugly_number[i] == hq[0][0]: # remove the duplicated same number for hq
                value, index, prime = heapq.heappop(hq) # pop the smallest number
                heapq.heappush(hq, (prime * ugly_number[index], index + 1, prime)) # index means the ugly number that haven't been multiplied by the prime.
        return ugly_number[-1]