将N条长度均为M的有序链表进行合并，合并后的链表也保持有序，

[单选题]

将N条长度均为M的有序链表进行合并，合并后的链表也保持有序，时间复杂度为( )

查看答案及解析

禁止你发言

1. 在每一个链表中取出第一个值，然后把它们放在一个大小为N的数组里，然后把这个数组当成heap建成小(大)根堆。此步骤的时间复杂度为O(N)：N个数构建一个堆的复杂度是O(N)

2. 取出堆中的最小值(也是数组的第一个值), 然后把该最小值所处的链表的下一个值放在数组的第一个位置。如果链表中有一个已经为空（元素已经都被取出），则改变heap的大小。此步骤的时间复杂度为O(lg N)。

3. 不断的重复步骤二，直到所有的链表都为空。

建堆只建一次，复杂度为O(N)；调整堆MN-1次（构建的时候抽走了根结点，剩下的数目是MN-1个数），复杂度为(MN-1)*O(lg N)。

4.复杂度是O(N)+(MN-1)*O(lg N)，所以复杂度为O(MN*lg N)

在堆排序中也是一样的，总共n个数，需要得到n个有序的数，那么构建堆需要O(n)，重建堆需要（n-1)*O(lgn)，所以总共复杂度O(nlgn)；如果我只需要前面k个数有序的，那么重构堆需要k*O(lgn)，那么总共复杂度就是O(klgn)

原文链接：https://blog.csdn.net/zz2230633069/article/details/103298915

发表于 2021-04-08 21:50:11 回复(0)