关注
这题应该是用快排的思想:例如找49个元素里面第24大的元素,那么按如下步骤: 1.进行一次快排(将大的元素放在前半段,小的元素放在后半段),假设得到的中轴为p 2.判断 p - low + 1 == k ,如果成立,直接输出a[p],(因为前半段有k - 1个大于a[p]的元素,故a[p]为第K大的元素) 3.如果 p - low + 1 > k, 则第k大的元素在前半段,此时更新high = p - 1,继续进行步骤1 4.如果p - low + 1 < k, 则第k大的元素在后半段, 此时更新low = p + 1, 且 k = k - (p - low + 1),继续步骤1. 由于常规快排要得到整体有序的数组,而此方法每次可以去掉“一半”的元素,故实际的复杂度不是o(nlgn), 而是o(n)。
点赞
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你想跟着什么样领导? #
5562次浏览 82人参与
# 什么样的背景能拿SSP? #
117345次浏览 410人参与
# 百度秋招 #
56015次浏览 394人参与
# 你的秋招白月光和意难平公司 #
7153次浏览 82人参与
# 分享一个让你热爱工作的瞬间 #
47487次浏览 412人参与
# 找实习是选平台还是选业务? #
10309次浏览 147人参与
# 从夯到拉,评价编程语言 #
5075次浏览 48人参与
# 秋招签约后的心态变化 #
106115次浏览 923人参与
# 职场吐槽大会 #
289790次浏览 2111人参与
# 每个月花钱最多的地方是? #
5351次浏览 76人参与
# xxx岗位的一天 #
10108次浏览 92人参与
# 作业帮求职进展汇总 #
77707次浏览 520人参与
# 十一月总结 #
13438次浏览 146人参与
# 你面试时吹过最大的牛 #
20311次浏览 116人参与
# 为什么国企只招应届生 #
218503次浏览 1262人参与
# 饿了么求职进展汇总 #
80318次浏览 684人参与
# 非技术求职现状 #
549566次浏览 3509人参与
# 实习学到最有价值的工作习惯 #
43662次浏览 378人参与
# 韶音科技求职进展汇总 #
65043次浏览 510人参与
# AI“智障”时刻 #
6092次浏览 54人参与
# 实习生如何通过转正 #
111801次浏览 1421人参与