0

我正在解决 Interviewbit 代码挑战Merge K Sorted Lists：

合并 k 个排序的链表并将其作为一个排序列表返回。

例子 ：

1 -> 10 -> 20
4 -> 11 -> 13
3 -> 8 -> 9

将导致

1 -> 3 -> 4 -> 8 -> 9 -> 10 -> 11 -> 13 -> 20

Python 模板代码为：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param A : list of linked list
    # @return the head node in the linked list
    def mergeKLists(self, A):
        pass

这是我的python 3解决方案：

from heapq import heapify, heappop, heappush
class Solution:
    # @param A : list of linked list
    # @return the head node in the linked list
    def mergeKLists(self, A):
        minheap = [x for x in A]
        # print(minheap)
        # heapify(minheap)
        # print(minheap)
        head = tail = None 
        # print(minheap)
        while minheap: 
            # print(minheap)
            heapify(minheap)
            print([x.val for x in minheap])
            minimum = heappop(minheap)
            print(minimum.val)
            if head is None:
                head = minimum
                tail = minimum
            else:
                tail.next = minimum
                tail = minimum
            
            if minimum.next:
                heappush(minheap, minimum.next)

        return head

使用未注释的打印命令，您会注意到在 while 循环的中间运行中，heappop返回最大的元素，就好像我们正在处理一个最大堆，但我们不是！据我所知，这就是答案出错的地方。任何人都可以提出为什么 heappop 会这样工作的原因吗？以及如何纠正？

4

1 回答 1

0

当我使用示例数据在本地运行您的代码时，出现以下错误：

    heapify(minheap)

TypeError：在和<的实例之间不支持ListNodeListNode

这是意料之中的。的模板定义ListNode不支持进行比较，并且 heapify 函数将需要比较给定列表中的项目。

由于该类ListNode已由代码挑战框架定义，因此最好不要尝试使该类具有可比性。

我建议将元组放在具有列表节点实例作为成员的堆上，但它们的属性值首先出现，然后是它们所来自val的列表的编号（in ）。A作为第三个元组成员，您最终将拥有节点本身。这样比较会起作用，因为元组在其成员存在时是可比较的。并且由于当第一个成员值相同时，第二个元组成员将成为决胜局，因此第三个元组成员（列表节点实例）将永远不会进行比较。

与您的问题无关，但您应该只 heapify once，而不是在循环的每次迭代中。堆上的动作（heappush, heappop）保持堆属性，所以不需要heapify第二次调用。如果你在每次迭代中都这样做，你实际上会破坏你从使用堆中获得的效率优势。

这是您的代码随该更改而更新：

from heapq import heapify, heappop, heappush

class Solution:
    def mergeKLists(self, A):
        # place comparable tuples in the heap 
        minheap = [(node.val, i, node) for i, node in enumerate(A)]
        heapify(minheap)  # call only once
        head = tail = None 
        while minheap: 
            # extract the tuple information we need
            _, i, minimum = heappop(minheap)
            if head is None:
                head = minimum
                tail = minimum
            else:
                tail.next = minimum
                tail = minimum
            
            minimum = minimum.next
            if minimum:
                # push a tuple, using same list index
                heappush(minheap, (minimum.val, i, minimum))

        return head
于 2022-01-22T15:44:22.907 回答