Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

O(n log k) time O(k) space min-heap solution

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

O(n) time selection solution

leetcode

stackoverflow