import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return minHead(a, n ,K);
    }
    private int minHead(int[] a, int n, int K){
        //用优先队列，生成最小堆，java默认是对顶元素最小，c++ 默认最大
        PriorityQueue<Integer> minHead = new PriorityQueue<>();
        for(int i = 0; i< K ; i ++){
            minHead.offer(a[i]);//遍历k 个元素入堆。堆顶元素最小
        }
        //优先队列

//由于找第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小heap

// 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去(堆这种数据具有内部shiftup , shiftdown 功能，自己维持最小堆。Java默认的是最小堆。)
        for(int j = K ; j < n ; j++){
            if(a[j] >= minHead.peek()){//遍历数组其他元素，如果比堆顶元素大的，继续入堆。
                minHead.poll();
                minHead.offer(a[j]);
                    
            }else{
                continue;
            }
        }
        
        return minHead.peek(); //遍历结束数组，最后堆顶就是第k 大的那个元素
        
        
        
    }
}

用最小堆：

/**

* topK 问题的第二种解法

* 时间复杂度：O(NlogK)，遍历数据 O(N)，堆内元素调整 O(K)；

* 空间复杂度：O(K)。

*/

//优先队列

//由于找第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小heap

// 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去(堆这种数据具有内部shiftup , shiftdown 功能，自己维持最小堆。Java默认的是最小堆。)

解法二： 快排

package testTopK;

public class L215 {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findKthLargest(new int[]{1,3,45,2,3,4,2,34}, 5));//测试用例
    }

}


class Solution {

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int targetIndex = len - k;//第k 大元素的下. 因为第k 大是从后面开始数的
        int low = 0, high = len - 1;
        while (true) {
            int i = quickSort(nums, low, high);


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

            if (i == targetIndex) {
                return nums[i];//最后返回这个
            } else if (i < targetIndex) {
                low = i + 1;
            } else {
                high = i - 1;
            }
        }
    }

    /**
     * 分区函数，将 nums[start] 作为 flag锚点
     * 一左，一右，两个指针，遍历数组，左边找比第一个数大的，右边找比flag小的，{左大右小}找到了就立马交换{左小右大}
     * 直到遍历指针相等，left == right , 这时候 将nums[i]和 flag 进行交换，返回下标 i，就是分区点的下标。
     */
    public int quickSort(int[] nums, int start, int end){ //返回int
//        if(start >= end){
//            return;
//        }不需要递归
        int left = start;
        int right = end;

        int flag = nums[start];
        while(left < right){
            while(left < right && nums[right] >= nums[start]){
                right--;//                    >=

            }
            while(left < right && nums[left] <= nums[start]){
                left++;
            }
            int temp = nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
        }
        //left == right
        nums[start] = nums[right];//nums[start] = nums[left];//交换锚点元素
        nums[right] = flag;
        return left;//return right;//返回下标。

//        quickSort(nums, start, left-1);//这是递归，原来的快排的代码，直到排序完成，这题不需要
//        quickSort(nums,left+1,end);

    }

}

大家加油：P