215. 数组中的第K个最大元素

刷题 leetcode

题目：在未排序的数组中找到第 k 个最大的元素。
示例1：输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例2：输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

此题考的就是排序

class Solution {
    //方法一：堆排序，创建k个元素的小顶堆
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for(int num : nums){
            heap.offer(num);//比堆顶元素大就进堆
            if(heap.size() > k){
                heap.poll();//顶部元素出堆
            }
        }
    }
    /**
     * 方法二：快速排序
     * 1.从数列中挑出一个元素，成为基准
     * 2.重新排序数列，元素比基准值小的摆在基准前面，比基准大的摆在基准后面，在此轮排序退出后，基准就处在数列的中间
     * 3.递归地把小于基准值元素的子数列和大于基准值元素的子数列依上面步骤排序
     */
    public int findKthLargest2(int[] nums, int k) {
        return quickSort(nums, k, 0, nums.length-1);
    }
    Random random = new Random();
    //对数组nums的区间[left,right]的元素进行快排
    private int quickSort(int[] nums, int k, int left, int right){
        int index = left+random.nextInt(right-left+1);
        int pivot=nums[index];
        nums[index]=nums[left];//先把最左边的元素提出来，产生一个坑位
        int L=left, R=right;
        while(L<R){
            while(L<R && nums[R]>=pivot) R--;   //找到右边第一个小于基准的元素
            nums[L]=nums[R];                    //将此元素填入左边的坑中(基准的左侧)
            while(L<R && nums[L]<=pivot) L++;   //找到左边第一个大于基准的元素
            nums[R]=nums[L];                    //将此元素填入右边的坑中(基准的右侧)
        }
        nums[L]=pivot;  //左右指针重合(L==R)后，将基准元素放回重合位置
        if(L==nums.length-k) return nums[L];
        //如果重合位置在目标位置左边，则对右边区间快排
        else if(L<nums.length-k) return quickSort(nums,k,L+1,right);
        else return quickSort(nums,k,left,L-1);//否则对左边区间快排
    }
}