方法一 最大堆

建立一个最大堆，把数据存进去，堆顶元素是最大的；
poll() k个数，最后一次poll出来的就是第K大的数。

import java.util.*;
public class Solution  {
    public int findKth(int[] a, int n, int K) {
        // write code here
        if (n < K)
            return -1;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((e1, e2) -> {
            return e2 - e1;
        });//大顶堆
        for (int i = 0; i < n; i++) {
            maxHeap.add(a[i]);
        }
        int res = 0;
        for (int i = 0; i < K; i++) {
            res = maxHeap.poll();
        }
        return res;
    }
}

方法二 快排思想

import java.util.*;

public class Solution  {
    public int findKth(int[] a, int n, int K) {
        // write code here
        if (n < K)
            return -1;
        return findKth(a, 0, a.length - 1, K);
    }
    private int findKth(int[] a, int start, int end, int k) {
        if (start <= end) {
            int pivot = Partition(a, start, end);//下标位置
            if (k - 1 == pivot) {
                return a[pivot];
            }
            else if (pivot < k - 1) {
                return findKth(a, pivot + 1, end, k);
            }
            else {
                return findKth(a, start, pivot - 1, k);
            }
        }
        return -1;
    }

    private int Partition(int[] a, int start, int end) {
        int left = start;
        int right = end;
        int pivot = a[left];
        //把比pivot大的移到左边，小的移到右边
        while (left < right) {
            while (left < right && a[right] <= pivot)
                right--;
            while (left < right && a[left] >= pivot)
                left++;
            if (a[left] < a[right]) {
                int temp = a[left];
                a[left] = a[right];
                a[right] = temp;
            }
        }
        a[start] = a[left];
        a[left] = pivot;
        return left;
    }
}