Reference: LeetCode EPI 11.8
Difficulty: Medium

Problem

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.

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

Example:

1
2
3
4
5
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Analysis

Methods:

  1. Sorting
    • Sort the array and find the index num.length - k element.
      1
      2
      3
      4
      5
      sort
      public int findKthLargest(int[] nums, int k) {
      Arrays.sort(nums);
      return nums[nums.length - k];
      }

Time: $O(N\log{N})$ 3 ms
Space: $O(1)$

  1. Heap
    • Since our goal is to find the k-th largest element, we need a min heap to store k elements at any time.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      public int findKthLargest(int[] nums, int k) {
      PriorityQueue<Integer> minPQ = new PriorityQueue<>((n1, n2) -> (n1 - n2));
      for (int val : nums) {
      minPQ.add(val);
      if (minPQ.size() > k) {
      minPQ.poll();
      }
      }
      return minPQ.poll();
      }

Time: $O(N\log{k})$ 38 ms
Space: $O(k)$

  1. Quick Select
    • Using the partition algorithm in quicksort developed by Tony Hoare, also known as Hoare’s selection algorithm.
    • For simplicity, k-th largest element is the same as (N - k)-th smallest element, we then we can implement k-th smallest algorithm for this problem.
    • Notice that this algorithm works well even for arrays with duplicates.
    • Notice that randomly picking a pivot will bring about great performance improvement. Swap the randIdx‘s element with the one at lo.
      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
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      public int findKthLargest(int[] nums, int k) {
      int n = nums.length;
      return quickSelect(nums, n - k, 0, n - 1); // (n-k)-th (from 0)
      }

      // find the k-th element (from 0 ~ hi - 1)
      private int quickSelect(int[] nums, int k, int lo, int hi) {
      if (lo == hi) { // base case: only one item
      return nums[lo];
      }

      // swap randIdx
      Random rand = new Random();
      int randIdx = lo + rand.nextInt(hi - lo + 1);
      swap(nums, lo, randIdx);

      int p = lo, i = lo, j = hi + 1; // one offset

      while (true) {
      while (nums[++i] < nums[p]) { // move i
      if (i == hi) break;
      }
      while (nums[--j] > nums[p]) { // move j
      if (j == lo) break;
      }
      if (i >= j) break;
      swap(nums, i, j);
      }

      swap(nums, p, j);

      if (k < j) {
      return quickSelect(nums, k, lo, j - 1);
      } else if (k > j) {
      return quickSelect(nums, k, j + 1, hi);
      } else {
      return nums[j];
      }
      }

      private void swap(int[] nums, int i, int j) {
      int temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
      }

Time: $O(N)$ in the average case; $O(N^2)$ in the worst case. 1 ms
Space: $O(1)$


Comment