关注
其实有点震惊出这个题,典型的quick select问题,我贡献一个我的代码供参考吧 def findKthLargest(nums, start, end, k):
if start >= end:
return nums[end]
left, right = start, end
pivot = nums[left + (right - left) / 2]
while left <= right:
while left <= right and nums[left] > pivot:
left += 1
while left <= right and nums[right] < pivot:
right -= 1
if left <= right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
if start + k - 1 <= right:
return findKthLargest(nums, start, right, k)
if start + k - 1 >= left:
return findKthLargest(nums, left, end, k - (left - start))
return nums[right + 1]
其实就是典型的快速排序变体而已,while循环中关于pivot的那两个大小于号一改上面这个函数就变成快排了,个人觉得这个很好记忆而且是单独找这种第k大第k小之类问题的最优解了
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享


点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 工作中哪个瞬间让你想离职 #
28379次浏览 197人参与
# 在职场上,你最讨厌什么样的同事 #
16282次浏览 162人参与
# 选了这个offer,你有没有后悔? #
592990次浏览 4028人参与
# 小米硬件提前批进度交流 #
171106次浏览 1528人参与
# 机械人,秋招第一次笔试的企业是哪家? #
41143次浏览 327人参与
# 哪些公司校招卡第一学历 #
74550次浏览 304人参与
# 担心入职之后被发现很菜怎么办 #
139374次浏览 809人参与
# 入职以后才知道的校招谎言 #
88988次浏览 587人参与
# 华子oc时间线 #
1245015次浏览 6487人参与
# Offer比较,你最看重什么? #
192149次浏览 1310人参与
# 哪些公司开提前批了? #
29866次浏览 277人参与
# 风评不好的公司,你会去吗? #
65849次浏览 463人参与
# 两会劳动法放大招 #
76705次浏览 692人参与
# 实习如何「偷」产出? #
55996次浏览 1391人参与
# 职场常用语录大全 #
4081次浏览 30人参与
# 不卡学历的大厂有哪些? #
32597次浏览 246人参与
# 校招阶段,学历VS技术哪个更重要? #
19445次浏览 205人参与
# 机械人春招想让哪家公司来捞你? #
349554次浏览 3088人参与
# 除了主业以外,你还有哪些其他收入? #
13563次浏览 203人参与
# 工作丧失热情的瞬间 #
294431次浏览 2373人参与