第K大元素

来自Leetcode第215题数组中的第K大元素

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

示例 1:

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

---

partition

利用快速排序里的partition过程实现。参考

partition（切分）操作，使得：

• 对于某个索引 j，nums[j] 已经排定，即 nums[j] 经过 partition（切分）操作以后会放置在它 “最终应该放置的地方”；
• nums[left] 到 nums[j - 1] 中的所有元素都不大于 nums[j]；
• nums[j + 1] 到 nums[right] 中的所有元素都不小于 nums[j]。

int []nums;
    private static Random ran = new Random(System.currentTimeMillis());
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0, right = len - 1;
        int target = len - k;
        this.nums = nums;
        int index;
        while(true){
            index = partition(left,right);
            if(index < target)
                left = index + 1;
            else if(index > target)
                right = index - 1;
            else
                return this.nums[index];
        }
    }

    private int partition(int left,int right){
        //在区间随机选择一个点作为枢纽
        if(right > left){
            int index = left + 1 + ran.nextInt(right - left);
            swap(left,index);
        }
        int pivot = nums[left];
        int j = left;
        for(int i = left + 1 ; i <= right ; i++){
            if(this.nums[i] < pivot){
                //小于枢纽的交换位置
                j++;
                swap(j,i);
            }
        }
        // 在之前遍历的过程中，满足 [left + 1, j] < pivot，并且 (j, i] >= pivot
        // 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot
        swap(j,left);
        return j;
    }

    private void swap(int left,int right){
        int temp = this.nums[left];
        this.nums[left] = this.nums[right];
        this.nums[right] = temp;
    }

优先队列

参考

优先队列的思路是很朴素的。因为第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小堆：

1、如果当前堆不满，直接添加；

2、堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，只有新都到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构。

说明：这里最合适的操作其实是 replace，即直接把新读进来的元素放在堆顶，然后执行下沉（siftDown）操作。Java 当中的 PriorityQueue 没有提供这个操作，只好先 poll() 再 offer()。

优先队列的写法就很多了，这里例举一下我能想到的（以下的写法大同小异，没有本质差别）。

假设数组有 len 个元素。

思路1：把 len 个元素都放入一个最小堆中，然后再 pop() 出 len - k 个元素，此时最小堆只剩下 k 个元素，堆顶元素就是数组中的第 k 个最大元素。

思路2：把 len 个元素都放入一个最大堆中，然后再 pop() 出 k - 1 个元素，因为前 k - 1 大的元素都被弹出了，此时最大堆的堆顶元素就是数组中的第 k 个最大元素。

思路 3：只用 k 个容量的优先队列，而不用全部 len 个容量。

import java.util.PriorityQueue;

public class Solution {

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        // 使用一个含有 k 个元素的最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
        for (int i = 0; i < k; i++) {
            minHeap.add(nums[i]);
        }
        for (int i = k; i < len; i++) {
            // 看一眼，不拿出，因为有可能没有必要替换
            Integer topEle = minHeap.peek();
            // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
            if (nums[i] > topEle) {
                minHeap.poll();
                minHeap.add(nums[i]);
            }
        }
        return minHeap.peek();
    }
}