/ Data Structure and Algorithms  

Leetcode 215. Kth Largest Element in an Array

Question



Find the kth largest number in an array.

Similar Questions

Solution - Brute Force

Use quick sort to sort from large to small, and return the kth number.

We can directly use the sorting algorithm provided by java, and because the default is to sort from small to large, so we can return the last kth number.

Solution - Priority Queue

We can use the priority queue to build a maximum heap, and then pop the elements in turn. The kth element that is popped is what we are looking for.

Here we can use the PriorityQueue provided by java.

Java default is to build the minimum heap, so we need a Comparator to change the priority.

Introduction to PriorityQueue can be found here: Priority Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findKthLargest(int[] nums, int k) {
    Comparator<Integer> comparator = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    };

    // create priority queue
    Queue<Integer> queue = new PriorityQueue<>(comparator);
    for (int num : nums) {
        queue.offer(num);
    }

    for (int i = 0; i < k - 1; i++) {
        queue.poll();
    }

    return queue.poll();
}