无序单向链表排序的时间复杂度---拼多多二面编程题

无序单向链表排序的时间复杂度,我认为最快是O(n^2)--->冒泡排序
1归并排序 查找中间元素O(n)
2快排->无法向前遍历
3堆排序-》不会
大家知道有更快的算法吗
#笔试题目#
全部评论
归并排序,两两合并就行,每次合并规模扩大就行,不用找中间元素,复杂度nlogn
点赞 回复 分享
发布于 2020-10-29 20:05
归并排序是NlgN 的 这是我一面的题,你这也太爽了😁 简单分析一下,一共lgN层 每层merge和找中点都是O(N)的
点赞 回复 分享
发布于 2020-10-29 20:08
我知道一种快排写法是可以用在单向链表的
点赞 回复 分享
发布于 2020-10-29 20:24
懂了 谢谢各位
点赞 回复 分享
发布于 2020-10-29 21:19

相关推荐

我现在一边实习、一边准备秋招,还在考公。实习工作比较轻松,闲暇时投投简历,但每天都不知道自己在干嘛,感觉很空虚。开始备考后,心里突然安定下来,仿佛找到了高考前的目标,每天都有新知识进脑,心态也变得平和。与其全心投入秋招,不如利用时间充实自己,学习一些感兴趣的东西。当然,拿到offer当然好,没拿到也至少能收获成长。人生是自己的,疲惫时按下暂停键,保持对生活的热情才是最重要的!
牛客728883471号:主要是牛客上的程序员偏多,对程序员来说,进一步跟退一步差别可就太大了。同样的985硕,找到好一点的工作能年薪60多万,运气差一点可能offer都接不到。不像咱们传统制造业,好的坏的工作收入差异没这么大。我以前读的土木更是,哪有什么人去实习,大四快毕业还有半年了才开始找。最后有的去工地当监理,有的保/考研,有的去银行,有的考公,有的回老家当村官。都是一个月几千块,差别不大
点赞 评论 收藏
分享
牛舌:如果我不想去,不管对方给了多少,我一般都会说你们给得太低了。这样他们就会给下一个offer的人更高的薪资了。
点赞 评论 收藏
分享
点赞 1 评论
分享
牛客网
牛客企业服务