小根堆O(N*logN)

  /*法一： 小根堆 时间复杂度O(N * logN)
    */
    public int findKthLargest1(int[] nums, int k) {
        //小根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) ->{
            return o1 - o2;
        });
        //把k个数先加进去
        for (int i = 0; i < k; i++) {
            minHeap.add(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.add(nums[i]);
            }
        }
        return minHeap.peek();
    }

借鉴快排思路O(N)

 /*法二：借鉴快排思路
     */
    public int findKthLargest2(int[] nums, int k) {
        return process(nums, 0, nums.length - 1, nums.length - k);
    }
    //num[L..R]范围上，如果排序的话(不是真的排序)，找位于index的数
    public static int process(int[] num, int L, int R, int index) {
        if (L == R) {
            return num[L];
        }
        int pivot = num[L + (int) (Math.random() * (R - L + 1))];
        int[] range = partition(num, L, R, pivot);
        if (index >= range[0] && index <= range[1]) {
            return num[index];
        } else if (index < range[0]) {
            return process(num, L, range[0] - 1, index);
        }else {
            return process(num, range[1] + 1, R, index);
        }

    }

    private static int[] partition(int[] num, int L, int R, int pivot) {
        int less = L - 1;
        int more = R + 1;
        int cur = L;
        while (cur < more) {
            if (num[cur] < pivot) {
                swap(num, ++less, cur++);
            } else if (num[cur] > pivot) {
                swap(num, --more, cur);
            } else {
                cur++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

    private static void swap(int[] num, int i, int j) {
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }

面试吹：bfprt算法