排序的方法就不说了
这里记录一下o(n)复杂度的算法
思想，利用快速排序的划分思想，每一次划分会有一个元素处于最终位置
判断这个位置，若所处位置大于k，则向左边寻找
若所处位置大于k，向右边寻找。
第k大的数，是指数组从小到大排序完后右边往左数第k个，也就是左边往右数下标nums.size()-k 位置的数
class Solution {
public:
int divide(vector<int> &nums, int left, int right){
int middle = nums[left];
while(left<right){
while(left<right&&nums[right]>=middle) right--;
nums[left]=nums[right];
while(left<right&&nums[left]<=middle) left++;
nums[right]=nums[left];
}
nums[left]=middle;
return left;
}
int find_K(vector<int> &nums, int left, int right, int k){
if(left==right){
if(k==left)
return nums[left];
else
return -1;
}
int c = divide(nums, left, right);
if(k==c){
return nums[c];
}else if (k<c){
return find_K(nums,left,c-1,k);
}else{
return find_K(nums,c+1,right,k);
}
}
int findKthLargest(vector<int>& nums, int k) {
int r = find_K(nums,0,nums.size()-1, nums.size()-k);
return r;
}
};
原文链接: https://www.cnblogs.com/lxzbky/p/12493706.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/400057
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
