合并 K 排序列表的时空复杂性

Question

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

如果n是ArrayList的大小CCD_ 2是最长链表的长度

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

空间复杂度：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<ListNode>，而不是PriorityQueue<Integer>。当然，您必须编写一个自定义比较器来对ListNode的值进行排序。

现在，当您轮询堆时，您会得到位于该列表顶部的ListNode。如果该节点的next不为null，则将next推回到堆中。如果节点的next为null，那么您处于该列表的末尾，并且不会将任何内容推回到堆中。

它看起来像：

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;