将 N 条长度均为 M 的有序链表进行合并,合并以后的链表也保持有序,时间复杂度为 1 。-笔试面试资料

这是qklbishe.com第10056 篇笔试面试资料
提供答案分析,通过本文《将 N 条长度均为 M 的有序链表进行合并,合并以后的链表也保持有序,时间复杂度为 1 。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
将 N 条长度均为 M 的有序链表进行合并,合并以后的链表也保持有序,时间复杂度为 1

将 N 条长度均为 M 的有序链表进行合并,合并以后的链表也保持有序,时间复杂度为 1  。 jack_kuo
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)

2021-04-24 16:11:29 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 将 N 条长度均为 M 的有序链表进行合并,合并以后的链表也保持有序,时间复杂度为 1 。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情