Skip to content

Latest commit

 

History

History
46 lines (33 loc) · 1.59 KB

313.md

File metadata and controls

46 lines (33 loc) · 1.59 KB

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]