LeetCode link

Intuition

  • Using minHeap to save the top k largest numbers, and the root is the kth largest number.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || k > nums.length) {
            return Integer.MIN_VALUE;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int num: nums) {
            if (minHeap.size() < k) {
                minHeap.add(num);
            } else {
                if (num >= minHeap.peek()) {
                    minHeap.poll();
                    minHeap.add(num);
                }
            }
        }
        return minHeap.peek();
    }
}