核心思路在于如何找到下一个最小的丑陋数字加入数组中,故创建一个�heap,结构如下:
- value:是当前这个节点的数值,也是丑陋数字,但是不一定是最小的
- index:当前prime的第一个还未乘过的丑陋数字
- prime:当前prime
可以把每一个节点当作当前prime的序列,其中index意味着这个系列的下一个最小值是多少,因为当前dq里面保存了之前的每一轮prime系列当前的数字,所以只要存在其他系列的数字小于当前系列的下一轮数字,dq就会发生转换,保证了dq的最小值即为下一个丑陋数字的最小值
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]