合并K排序列表的时间和空间复杂度

Question

我为提到的问题编写了这个解决方案，因为我对堆不太熟悉，所以我很难找到复杂性，复杂性分析中的任何建议/更正都会有所帮助。

如果

n

是ArrayList的大小

m

是最长链表的长度

根据我的说法，复杂性应该如下

空间复杂度：

O(nm)

（对于堆）

时间复杂度：

O(nm)

（怀疑这个）

public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> a) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(ListNode node: a) {
            while(node != null) {
                minHeap.add(node.val);
                node = node.next;
            }
        }

        ListNode head = new ListNode(0);

        ListNode temp = head;
        while(minHeap.size() > 0) {
            ListNode newNode = new ListNode(minHeap.poll());
            temp.next = newNode;
            temp = temp.next;
        }

        return head.next;
    }
}

Answer 1

如果您有

k

个排序列表和

n

总共元素，那么合并列表的时间复杂度为 O(n * log(k))。所需的堆空间为O(k)。这是它的工作原理。

首先创建堆，并将每个链表的头节点创建到其中。因此，您将拥有一个

PriorityQueue<Integer>

，而不是

PriorityQueue<ListNode>

。当然，您必须编写一个自定义比较器来对

ListNode

的值进行排序。

现在，当您轮询堆时，您会在该列表的头部看到

ListNode

。如果该节点的

next

不为空，则将

next

推回到堆上。如果节点的

next

为空，那么您位于该列表的末尾，并且不会将任何内容推回到堆上。

看起来像：

ListNode head = new ListNode(0);
ListNode temp = head;

for each ListNode in a
  minHeap.add(a)

while minHeap is not empty
  node = minHeap.pop()
  if node.next is not null
    minHeap.push(node.next)
  temp.next = node;
  temp = node;

return head.next;

        
  
  

Answer 2

正如 Jim Mischel 所建议的，您需要

ListNode

的堆或优先级队列，按

ListNode.value

排序。在 Java 中，您可以通过提供按值进行比较的自定义

Comparator[ListNode]

来实现此目的。

这里有一些关于复杂性的更多细节；我将从空间复杂度开始。首先将所有

n

列表添加到堆中。这是堆的最大大小，因此空间复杂度为

O(n)

。 输入列表的大小不会影响算法使用的空间，您将在堆/中使用相同的

O(n)

元素无论最大列表长度是

m=1

还是

m=1e9

，都在开头排队。所以这就是为什么它不是

O(m*n)

。

现在时间复杂度。在最坏的情况下，所有

n

列表都具有相同的最大元素数

m

，我们将从其中循环弹出元素。每当您从堆中弹出一个元素，或从优先级队列中删除某些内容时，都需要

O(log(n))

操作。这是因为最坏的情况是弹出顶部元素，将最后一个元素放在顶部，然后必须将其一直筛选到堆的底部。堆是平衡的，因此它有

O(log(n))

层。因此，这需要

O(log(n))

交换，从而需要总操作。

我们将为每个元素执行

O(log(n))

操作。在最坏的情况下，每个列表的长度都相同，有

O(m*n)

个元素

m

，所以总时间复杂度为

O(m*n*log(n))

。