Skip to main content
 首页 » 编程设计

python之python heapq 合并的内部工作。它如何在不生成列表的情况下对列表进行排序

2025年05月04日10JustinYoung

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如果需要,可以直接。

您可能会从实现它的模块中猜到,它使用堆来合并传递给它的可迭代对象。如果可迭代对象(在本例中为生成器)每个都按顺序产生它们的值,它将组合它们,以便它产生的值也按顺序产生。它不会消除重复值,这就是为什么您显示的代码会检查最新值是否等于前一个值。