如何使用快速排序的思想从有重复数据的数据中找出第k大的元素,
例如[9,8,8,7,7,6,5,4,3]中第3大的元素是7。
有大佬知道怎么求解吗?
例如[9,8,8,7,7,6,5,4,3]中第3大的元素是7。
有大佬知道怎么求解吗?
全部评论
快速选择算法,复杂度On
快排但是不要取两边都做,只做一边就好
leetcode215,高频考题
快选算法,topK经典题了
个人觉得堆排序简单,构造出堆就行了
快速排序,
第一次将数据分为【left,mid】[mid,right] ,如果【left,mid】中的数据个数等于k ,此时mid就是第k 大的数
如果【left,mid】中的数据个数小于k ,从[mid,right]中找到第k-【left,right】大的数
如果【left,mid】中的数据大于k ,从【left,mid】中找到第k 大的数
最小堆
改一下快速选择算法就好了,在快速选择的过程中维护一个变量记录前面有多少个去重后的数
快排和堆都可以,我个人比较推荐堆
了解一下快速选择算法,只做一遍就好了,说白了其实就是对树做了剪枝
快排,每次你能知道pivot的位置,pivot的位置比k大就去排后面,否则排前面,直到pivot=k为止
先去重在排序就好了呀
建议用最大堆,取到相同的元素不累减k就好
快速选择
你想想,快排 第一趟 跑出来 就能得知有几个大数,有几个小数了
去重快速选择
我只能想到快排后从左往右去一遍重,也就再遍历一遍,复杂度也不高。看评论区感觉好多人没注意到是去重后的第k大。
快排复杂度可以到On
快速选择,算法导论讲过。我之前面试被面试官要求证明复杂度🤣
堆排序,重复的不算就好了
用堆排序
相关推荐
05-21 12:39
汕头大学 数据分析师 点赞 评论 收藏
分享