heapq.merge() 如何在不生成列表的情况下对列表进行排序?
不知道我说清楚没有。
所以,这是从 Super Ugly Number problem at leetcode .
还有这段 python 代码
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
merged = heapq.merge(*map(gen, primes))
while len(uglies) < n:
ugly = next(merged)
if ugly != uglies[-1]:
uglies.append(ugly)
return uglies[-1]
让我很难理解它。在我搜索了“yield”和“heapq”的概念之后,我仍然没有在 while 循环中得到它,merged 如何知道 ugly in uglies >n 不会小于 uglies[n-1]。
请您参考如下方法:
heapq.merge的实现是纯Python,你可以read its code如果需要,可以直接。
您可能会从实现它的模块中猜到,它使用堆来合并传递给它的可迭代对象。如果可迭代对象(在本例中为生成器)每个都按顺序产生它们的值,它将组合它们,以便它产生的值也按顺序产生。它不会消除重复值,这就是为什么您显示的代码会检查最新值是否等于前一个值。
