leetcode215-数组中的第K个最大元素

思路

• 我自己想到的是用排序，然后取下标为n-k的数字，但是这样时间复杂度是O(nlogn)，不符合题目要求
• 题解中的快速排序法很好，我也想到了快速排序，但是具体实现没有写出来

要点

• 快速排序的递归中会往划分后的两边走，因此复杂度是O(nlogn)，而本题中只往一个方向走，因此复杂度是O(n)
• 一开始写的代码一直出bug，后来发现是我把变量cur停留的最终位置当成了基准元素，其实cur只是遍历数组的临时变量，和最后的结果毫无关系；想象一下一个数组已经是从小到大排序好的，选取第一个元素为基准元素，那么最后cur会走到末尾，而r会走到下标为0的位置。

代码

class Solution {

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums,0,nums.length-1,k);
    }

    private void swap(int[]nums,int l,int r){
        int t=nums[l];
        nums[l]=nums[r];
        nums[r]=t;
    }

    private int quickSelect(int[]nums,int left,int right,int k){
        int p=left+new Random().nextInt(right-left+1);  //随机选取基准元素
        swap(nums,left,p);
        int pivotElement=nums[left];
        int l=left,r=right,cur=left; //l左边比pivot小，r右边比pivot大
        while(cur<=r){
            if(nums[cur]==pivotElement)
                cur++;
            else if(nums[cur]<pivotElement){
                swap(nums,l,cur);
                l++;
                cur++;
            }else {
                swap(nums,r,cur);
                r--;
            }
        }
        if(l<=nums.length-k && nums.length-k<=r)
            return nums[nums.length-k];
        else if(r<nums.length-k)
            return quickSelect(nums,r+1,right,k);
        else
            return quickSelect(nums,left,l-1,k);
    }
}