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