首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
将 N 条长度均为 M 的有序链表进行合并,合并以后的链表也
[填空题]
将 N 条长度均为 M 的有序链表进行合并,合并以后的链表也保持有序,时间复杂度为
1
。
查看答案及解析
添加笔记
求解答(0)
邀请回答
收藏(6)
分享
纠错
1个回答
添加回答
0
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)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
2017
游戏研发工程师
搜狐畅游
Java工程师
上传者:
小小
难度:
1条回答
6收藏
1124浏览
热门推荐
相关试题
在类的定义中可以有两个同名函数,这...
哔哩哔哩
游戏研发工程师
2020
评论
(0)
下面关键字中,哪一个不是用于异常处...
哔哩哔哩
游戏研发工程师
2020
评论
(1)
下列各项中,不属于反映会计信息质量...
搜狐畅游
职能
2019
财务
评论
(2)
明明的随机数
数组
评论
(3692)
来自
华为研发工程师编程题
已知a
40
=...
京东
职能
2019
财务
保险
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题