anycode3 level
获赞
15
粉丝
1
关注
3
看过 TA
0
电子科技大学
2020
C++
IP属地:四川
暂未填写个人简介
私信
关注
2019-09-21 23:28
已编辑
电子科技大学 C++
0 点赞 评论 收藏
分享
2019-09-20 17:48
电子科技大学 C++
0 点赞 评论 收藏
分享
2019-08-31 18:52
已编辑
电子科技大学 C++
如题。 LeetCode215.数组中的第k个最大元素。 如果选择快排的一个思想,即分区的思想,他的时间复杂度为何是O(n)呢,应该如何分析呢?
王哥888号娇妻:快速选择其实相当于用二分法找这个第k大的元素,第一次partition需要遍历n个元素,假设第一次遍历后返回j,说明前j小的数都在前半段,如果k要比j小,那么就应该继续在前半段找这个第k小数,否则在后半段(和二分法找某个数一样的思想),这样下次遍历就是遍历j个或者n-j个。理想来说,partition应该刚刚把数组平分,因此总遍历数是n+n/2+n/4+...+1=o(n)
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客网在线编程
牛客网题解
牛客企业服务