Kth Element

快速排序

使用快排将数组排序，选取排好序的第 K 个元素，时间复杂度O(nlogn)，空间复杂度O(1)

public int getKthLargest(int[] nums, int k){
    Arrays.sort(nums);
    return nums[nums.length-k];
}

堆排序

维护大小为 K 的小顶堆，首先建立大小为K的小顶堆，第 K+1 元素加入堆时与堆顶元素比较大小，如果大于堆顶元素，则替代堆顶元素，重新调整堆成为小顶堆；直到遍历完剩下的元素；时间复杂度为O(nlogK)，空间复杂度O(K).

public int getKthLargest(int[] nums, int K){
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for(int val : nums){
        heap.add(val);
        if(heap.size > k)
            heap.poll();
    }
    return heap.peek();
}

快速选择

根据快速排序分区操作的特性：分区操作将小于基准值的元素分在基准左边，大于分在右边，并返回基准值下标；如果返回的基准值下标正好是 K ，则完成；平均时间复杂度O(n)，最坏时间复杂度O(n²)，空间复杂度O(1)。

public int getKthLargest(int[] nums, int K){
    int l = 0, h = nums.length-1;
    while(l <= h){
        int partitionInd = partition(nums, l, h);
        if(partitionInd == k-1)
            return nums[partitionInd];
        else if(partitionInd < k-1)
            h = partitionInd-1;
        else
            l = partitionInd+1;
    }
    return 0;
}

public int partition(int[] nums, int l, int h){
    if(l==h)
        return l;
    int pivot = nums[l];
    while(l<h){
        while(nums[h]>=pivot && l<h)
            h--;
        nums[l] = nums[h];
        
        while(nums[l]<=pivot && l<h)
            l++;
        nums[h] = nums[l];
    }
    nums[l] = pivot;
    return l;
}

TopK Element

用于求解 TopK Elements 问题，通过维护一个大小为 K 的堆，堆中的元素就是 TopK Elements。

堆排序也可以用于求解 Kth Element 问题，堆顶元素就是 Kth Element。

快速选择也可以求解 TopK Elements 问题，因为找到 Kth Element 之后，再遍历一次数组，所有小于等于 Kth Element 的元素都是 TopK Elements。