题目描述

在未排序的数组中找到第K个最大的元素。请注意，你需要找的是数组排序后的第K个最大的元素，而不是第K个不同的元素。

示例一：
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例二：
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

题解

使用JAVA自带的优先队列，先将所有的元素依次放入堆中，然后弹出K次即可。需要注意的是要自己定义比较器，因为优先队列结构默认的排列顺序是自然排列。

自解(大根堆解法)

自己的解法是直接创建大根堆，然后排序后弹出第K个堆顶。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i : nums) {
            queue.add(i);
        }
        int result = 0;
        for (int i = 0; i < k; i ++) {
            result = queue.poll();
        }
        return result;
    }
}

小根堆解法

堆中维护当前扫描到的最大K个数，其后每一次的扫描到的元素，若大于堆顶，则入堆，然后删除堆顶；依此往复，直至扫描完所有元素。具体代码如下：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minQueue = new PriorityQueue<>(k);
        for (int num : nums) {
            if (minQueue.size() < k || num > minQueue.peek()) {
                minQueue.offer(num);
            }
            if (minQueue.size() > k) {
                minQueue.poll();
            }
        }
        return minQueue.peek();
    }
}

Partition 分区方法

此方法借助的是快排算法思想。每次分区操作开始时指定一个区分值，通过逐个比较将小于该值的元素放在左区，将大于该值的元素放在右区，然后将该区分元素放在左区和右区中间，分区函数返回值即为该元素所在的下标。
与此题目不同的地方在于，快排在每次分区后需要将左右两区继续递归下去，最终使得整个数组严格排序。但是该题目是挑选出第K大的元素即可，所以每次分区后只需要在目标分区中继续寻找即可。
现在思考如何借助 partition 分区来帮助找到第K大元素
如果 pivot 点刚好是第K大元素，那么它的左边一定有 K-1 个不小于它的元素，它的下标应该是 len-k（数组最末尾是 len-1）
所以

当 partition 函数返回的下标 i=len-k，则 arr[i] 就是我们要求的第K大元素
当 partition 函数返回的下标 i<len-k，那么说明第K大元素在下标 i 的右边，我们继续分区在 arr[i+1, len-1] 区间内查找：partition(arr, i+1, len-1)
当 partition 函数返回的下标 i>len-k，那么说明第K大元素在下标 i 的左边，我们继续分区在 arr[0, i-1] 区间内查找：partition(arr, 0, i-1)

　　以下是快速排序的实现：

quick_sort(int[] arr, int low, int high) {
    if (low >= high) return;
    int i = partition(arr, low, high);
    quick_sort(arr, low, i-1);
    quick_sort(arr, i+1, high);
}

完整代码为:

public class lc215 {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        quickSort(nums, 0, len-1, len-k);
        return nums[len-k];
    }

    private void quickSort(int[] nums, int left, int right, int target) {
        if (left>right){
            return;
        }

        int pIndex = partition(nums, left, right);
        if (pIndex==target){
            return;
        }else if (pIndex>target){
            quickSort(nums, left, pIndex-1, target);
        }else {
            quickSort(nums, pIndex+1, right, target);
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int lt = left;

        for (int i= left+1;i<=right;i++){
            if (nums[i]<pivot){
                lt++;
                swap(nums, lt, i);
            }
        }
        swap(nums, lt, left);
        return lt;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}