https://leetcode.com/problems/kth-largest-element-in-an-array/

Question

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.

Solution

The naive way of doing this is to sort the array nums and then return nums[nums.length - k].O(NlogN)

Further, we can do better by using a Priority Queue, which has complexity of O(NlogK):

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(k + 1);
        for (int num : nums) {
            pq.offer(num);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        return pq.peek();
    }
}

Better, use quick select. The basic idea is like quick sort to partition the array by a pivot. Compare the index of pivot with k to decide which part to go.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickselect(nums, 0, nums.length - 1, nums.length - k); // kth larget = length - k + 1 smallest
    }
    private int quickselect(int[] nums, int left, int right, int target) {
        int l = left;
        int r = right;
        while (l < r) {
            if (nums[l] > nums[right]) {
                r--;
                swap(nums, l, r);
            } else {
                l++;
            }
        }
        swap(nums, l, right);
        if (l == target) {
            return nums[l];
        } else if (l < target) {
            return quickselect(nums, l + 1, right, target);
        } else {
            return quickselect(nums, left, l - 1, target);
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}