python - 力扣 : Problem 23 - Merge K Sorted Lists

Question

problem LeetCode 上的表述如下:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6

我能够通过 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 个链表。

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

为了更好的时间，您需要将实现更改为:

• 使用堆将 min_idx 操作减少到 O(log k) 而不是 O(k) 是 k 个列表的数量
• 只需将所有内容放入一个数组，对其进行排序，然后将其放回 ListNode
• 在 O(最长列表的长度)中合并 2 个列表，并递归地成对合并，直到剩下 1 个