快速选择算法的时间复杂度分析

如题。
LeetCode215.数组中的第k个最大元素。
如果选择快排的一个思想，即分区的思想，他的时间复杂度为何是O(n)呢，应该如何分析呢?

#leetcode#
全部评论
快速选择其实相当于用二分法找这个第k大的元素，第一次partition需要遍历n个元素，假设第一次遍历后返回j，说明前j小的数都在前半段，如果k要比j小，那么就应该继续在前半段找这个第k小数，否则在后半段（和二分法找某个数一样的思想），这样下次遍历就是遍历j个或者n-j个。理想来说，partition应该刚刚把数组平分，因此总遍历数是n+n/2+n/4+...+1=o(n)
2 回复 分享
发布于 2019-08-31 19:09

相关推荐

02-03 20:40
清华大学 Java
点赞 评论 收藏
分享
昨天 14:23
西安建筑科技大学 数据分析师
点赞 评论 收藏
分享
2025-12-17 17:53
门头沟学院 Web前端
凉经
终于知道网上jd面经什么辣么少了
海梨花：我之前面试也是问我非技术问题，问过我怎么统计北京出租车数量，不借助任何网络或者其他平台的帮助，有足够多的人可以帮忙
点赞 评论 收藏
分享
02-06 21:46
西安财经大学 算法工程师
点赞 评论 收藏
分享
02-08 18:12
思摩尔国际（SMOORE）_研发工程师(准入职员工)
思摩尔内推，思摩尔内推码
思摩尔结构工程师一面一面技术面，面试官比较年轻，共23min1、面试官上来要求先说说你对思摩尔的了解2、自我介绍3、针对第一个项目的提问：项目背景？你承担的工作？你在项目中遇到的问题？你最大的收获？这些项目中设计的产品有在企业中应用过吗？没有应用的原因你觉得是什么？4、针对第二个项目的提问：在项目中成员有分歧怎么办？有人不配合怎么办？5、除了学校学习和项目科研的内容，你最近有学习过什么新技术吗？6、反问环节（最长的一次）面试官详细介绍了工作内容后续流程，还有总部的一轮面试思摩尔国际2026全球校园招聘倒计时❗还没拿到offer的同学抓紧时间⏰【急招岗位】①技术研发类硕士（24-30W）：产品企...
点赞 评论 收藏
分享
评论
1
4
分享

招聘动态

查看更多

27届简历点评

27届寒假/转正实习汇总

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 牛客吐槽大会 #
29211次浏览 336人参与
# 一份好的简历长什么样？ #
24196次浏览 442人参与
# 春节前，你还在投简历吗？ #
1274次浏览 26人参与
# 春节提前走，你用什么理由请假？ #
714次浏览 19人参与
# 春招什么时候投？ #
428次浏览 11人参与
# 材料专业就业可以去哪些企业岗位 #
55166次浏览 379人参与
# 一上班就想____，这正常吗？ #
17497次浏览 147人参与
# 刚入职就____，这样正常吗？ #
127639次浏览 670人参与
# 校招入职后的感受 #
479245次浏览 3664人参与
# 现在还是0offer，延毕还是备考 #
1283829次浏览 7925人参与
# 设计人秋招体验最好的公司 #
81088次浏览 735人参与
# 招聘要求与实际实习内容不符怎么办 #
166586次浏览 922人参与
# 你觉得机械有必要实习吗 #
73622次浏览 487人参与
# 携程求职进展汇总 #
867155次浏览 5663人参与
# 找实习多的是你不知道的事 #
1790760次浏览 20673人参与
# 机械人选offer，最看重什么？ #
158650次浏览 798人参与
# 设计人的面试记录 #
187668次浏览 1607人参与
# 我的秋招总结 #
280721次浏览 4334人参与
# 聊聊你的职场新体验 #
319588次浏览 1862人参与
# 为了减少AI幻觉，你注入过哪些设定？ #
9108次浏览 230人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务