牛客最菜应届生
牛客最菜应届生
全部文章
分类
题解(38)
归档
标签
去牛客网
登录
/
注册
牛客最菜应届生的博客
全部文章
(共4篇)
题解 | #寻找第K大#
思路 快排的思想,partition函数的使用。如果返回的pivot>n-K,那么right = pivot-1如果返回的pivot<n-K,那么left = pivot+1进行新一轮的partition,直到pivot = n-K 代码 class Solution { public:...
快速排序
2021-07-16
0
390
题解 | #寻找第K大#
思路 借助快排的Partition函数注意:1、是第K大,因此Partition返回的结果要和n-K比较!!! 代码 class Solution { public: int Partition(vector<int>& arr, int L, int R ){ ...
二分法
快速排序
数组
2021-07-11
0
241
题解 | #数组中出现次数超过一半的数字#
思路 参考《剑指offer》1、一个数字出现次数超过一半,那么排序后的中间位置的元素肯定就是这个要求的数字2、借助Partition函数,返回一个索引index,代表该位置的元素在排序后的数组中下标是index,比arr[index]小的都在左侧,比arr[index]大的都在右侧;3、根据inde...
快速排序
数组
二分法
2021-07-11
0
342
题解 | #最小的K个数#
思路 参考剑指offer1、首先使用快排的思想,对一个数组进行分割,大于某个值的在其右侧,小于某个值的在其左侧,该函数(Partition)返回一个索引,代表选择的数字的下标(可能有点绕)。2、然后就是根据这个返回的索引和k-1(需要k个数,下标范围就是0~k-1)比较,若返回的index<k...
快速排序
数组
2021-07-11
0
336