题解 | #寻找第K大#

java版
方法一：快排
很多人用快排最后一个用例会超时，解决方法是，随机的选取枢轴pivot。

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return quickSort(a, 0, n - 1, K);
    }
    
    private int quickSort(int[] nums, int low, int high, int target) {
        int i = low, j = high;
        // 随机选取枢轴，并将它与num[i]交换
        int rand = (int)(low + Math.random() * (high - low + 1));
        int temp = nums[rand];
        nums[rand] = nums[i];
        nums[i] = temp;
        int pivot = nums[i];
        while (i < j) {
            while (i < j && nums[j] < pivot) j--;
            if (i < j) {
                nums[i++] = nums[j];
            }
            while (i < j && nums[i] >= pivot) i++;
            if (i < j) {
                nums[j--] = nums[i];
            }
        }
        nums[i] = pivot;
        if (i == target - 1) {
            return nums[i];
        } else if (i < target - 1) {
            return quickSort(nums, i + 1, high, target);
        } else {
            return quickSort(nums, low, i - 1, target);
        }
    }
}

方法二：大顶堆

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        PriorityQueue<Integer> heap = new PriorityQueue<>((x, y) -> y - x);
        for (int i = 0; i < n; i++) {
            heap.offer(a[i]);
        }
        int res = -1;
        for (int i = 0; i < K; i++) {
            res = heap.poll();
        }
        return res;
    }
}

面试中可能会让你手撕堆排序，所以再来一个手撕堆排代码：

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        buildHeap(a, n);
        for(int i = n - 1; i > n - K; i--){
            swap(a, 0, i);
            sift(a, 0, i - 1);
        }
        return a[0];
    }
    
    private void buildHeap(int[] nums, int n){
        for(int i = n / 2 - 1; i >= 0; i--){
            sift(nums, i, n - 1);
        }
    }
    
    private void sift(int[] nums, int low, int high){
        int i = low;
        int j = 2 * i + 1;
        int pivot = nums[i];
        while(j <= high){
            if(j < high && nums[j] < nums[j + 1]){
                j++;
            }
            if(nums[j] > pivot){
                nums[i] = nums[j];
                i = j;
                j = 2 * i + 1;
            }else{
                break;
            }
        }
        nums[i] = pivot;
    }
    
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}