Leetcode215. 数组中的第K个最大元素(HOT100)

链接

第一次：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int n = nums.size();return nums[n-k];}
};

这显然不能出现在面试中，因为面试官考察的不是这个。

正确的代码：

class Solution{public:int quick_sort(vector<int>& nums,int l,int r,int k){if(l==r)return nums[k];//会保证第k小的数一直在递归的区间中，那么当区间里只有一个数的时候，就一定是要找的数了。int x = nums[l],i = l-1,j = r+1;while(i<j){do i++;while(nums[i]>x);do j--;while(nums[j]<x);if(i<j)swap(nums[i],nums[j]);}if(k<=j)return quick_sort(nums,l,j,k);else return quick_sort(nums,j+1,r,k);}int findKthLargest(vector<int>& nums,int k){return quick_sort(nums,0,nums.size()-1,k-1);//第k大，比如第1大，其实是降序排序后，索引为0的元素，第2大，就是索引为1的元素。//此题如果改为，找出第k小的元素，那么只需将do while(翻转这里的符号即可);}
};

使用的是快速选择算法，本质还是快排。 

快速选择算法具体而言：

1.先找个目标值也就是题目中的x，将数组分到两边，此时x左边都<=x，右边>=x
2.查看k是否<=左边个数，如果小于说明在左侧内，左侧递归排序即可找到K。反之在右边
3.最终无限夹击找到K