use generator to save storage and speed up program
class Solution(object):
def nthSuperUglyNumber(self, n, primes):
"""
:type n: int
:type primes: List[int]
:rtype: int
"""
uglies=[1]
def gen(prime):
for ugly in uglies:
yield ugly*prime
#*unpack the list of generators
merged=heapq.merge(*map(gen,primes))
while len(uglies)<n:
#the first time next() is called, the gen() will be initialized and all elements of primes will run through the generator once and yield one ugly*prime each and pushed to the heap. the other times next() is called, it will return the next smallest element in the heap meanwhile yield one ugly*prime and push onto the heap
ugly=next(merged)
if ugly!=uglies[-1]:
uglies.append(ugly)
return uglies[-1]
313. Super Ugly Number
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Write a program to find the nthsuper ugly number. Super u...
- Write a program to find the nth super ugly number. Super ...
- Ugly Number II Write a program to find the n-th ugly numb...
