LeetCode：问题23-合并K个排序列表

Question

LeetCode上说明的问题如下：

合并k个排序链表，并将其作为一个排序列表返回。分析并描述其复杂性。

例子：

输入：[1-

我能够通过131个测试案例中的129个，但在案例130中达到了“超出时间限制”。下面是我的实现。

有人能发现瓶颈吗？对提高时间复杂度有什么建议吗？

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

class Solution:
    # def print_lists(self, lists):
    #     idx = 0
    #     while idx < len(lists):
    #         ptr = lists[idx]
    #         _l = []
    #         while ptr is not None:
    #             _l.append(ptr.val)
    #             ptr = ptr.next
    #         idx += 1
    #         print(_l)

    def min_idx(self, lists):
        idx = 0

        for i in range(len(lists)):
            if lists[i] is None:
                continue
            elif lists[idx] is None:
                idx = i
            elif lists[i].val < lists[idx].val:
                idx = i
        return idx

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        head = tail = ListNode(-1)

        while len(lists) > 0:
            m_idx = self.min_idx(lists)

            if lists[m_idx] is None:
                return head.next

            tail.next = lists[m_idx]
            tail = tail.next
            lists[m_idx] = lists[m_idx].next

            if lists[m_idx] is None:
                del lists[m_idx]

        return head.next

我在没有使用del的情况下遇到了超过时间限制的问题。测试用例130包含10,000个LinkedList。

Answer 1

下面是一个更简单、更快速的代码版本，它避免了几个if：

def min_idx(self, lists):
    idx = 0

    for i in range(len(lists)):
        if lists[i].val < lists[idx].val:
            idx = i
    return idx

def mergeKLists(self, lists):
    head = tail = ListNode(-1)

    lists = list(filter(lambda x: x is not None, lists))

    while len(lists) > 0:
        m_idx = self.min_idx(lists)

        tail.next = lists[m_idx]
        tail = tail.next
        lists[m_idx] = lists[m_idx].next

        if lists[m_idx] is None:
            del lists[m_idx]

    return head.next

为了获得更好的效果，您需要将实现更改为：

• 使用heap将min_idx操作减少到O（log k），而不是O（k）是列表的数量