Question

Formatted question description: https://leetcode.ca/all/215.html

215. Kth Largest Element in an Array

Level

Medium

Description

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.

Example 1:

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

Output: 5

Example 2:

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

Output: 4

Note:

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

Algorithm

Heap or directly sorting can solve it, but kind of cheating.

The idea of Quick Sort, where the sorting direction is from big to small.

The core idea is to find a pivot point Pivot every time, and then traverse all other numbers, like this question from big to small, put the numbers greater than the pivot point to the left half, and put the numbers less than the pivot point to the right half. In the right half, the pivot point is the largest number in the entire array.

Although the left and right parts are not necessarily completely ordered, it does not affect the result of this question. Because all the values in the left half are greater than any value in the right half, we check the position of the pivot point:

  • If it happens to be k-1, then directly return the number at that position;
  • If it is greater than k-1, it means that the required number is in the left half, update the right boundary, and then find the new pivot point
  • otherwise, update the right half and find the position of the pivot

Code

Java

import java.util.Comparator;
import java.util.PriorityQueue;

public class Kth_Largest_Element_in_an_Array {

    public static void main(String[] args) {
        Kth_Largest_Element_in_an_Array out = new Kth_Largest_Element_in_an_Array();
        Solution s = out.new Solution();

        System.out.println(s.findKthLargest(new int[]{3,2,1,5,6,4}, 2)); // output: 5
    }


    class Solution {

        public int findKthLargest(int[] nums, int k) {

            int lo = 0;
            int hi = nums.length - 1;

            while (lo <= hi) {
                final int pos = partition(nums, lo, hi);
                if(pos == k - 1) {
                    return nums[pos]; // partially sorted, desc
                } else if (pos > k - 1) {
                    hi = pos - 1;
                } else { // pos < k - 1
                    lo = pos + 1;
                }
            }

            return -1; // or raise exception
        }

        private int partition(int[] nums, int lo, int hi) {

            int pivot = nums[lo], l = lo + 1, r = hi;
            while (l <= r) {
                if (nums[l] < pivot && nums[r] > pivot) {
                    swap(nums, l++, r--);
                }
                if (nums[l] >= pivot) ++l;
                if (nums[r] <= pivot) --r;
            }
            swap(nums, lo, r);
            return r;
        }

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

    }


    class Solution_heap {
        public int findKthLargest(int[] nums, int k) {

            final PriorityQueue<Integer> pq = new PriorityQueue<>();
            for(int val : nums) {
                pq.offer(val);

                if(pq.size() > k) { // if nums is already ordered, then poll() operation is N-2 times
                    pq.poll();      // and total O(n^(n-2)) => O(n^2)
                }
            }
            return pq.peek();
        }
    }

    class Solution_tooManyIfElse {
        public int findKthLargest(int[] nums, int k) {

            if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
                return -1;
            }

            // @note: Comparator.naturalOrder(), Comparator.reverseOrder()
            // @note: even define initial size as `k`, heap size here is unbound!
            PriorityQueue<Integer> heap = new PriorityQueue<>(k, Comparator.naturalOrder());

            int SIZE_LIMIT = k;
            int count= 0;
            for (int each: nums) {

                if (count < SIZE_LIMIT) {
                    heap.offer(each);
                    count++;
                } else {

                    if (each > heap.peek()) {
                        heap.poll();
                        heap.offer(each);
                    } else {
                        continue; // just for readibility
                    }
                }

            }

            return heap.poll();
        }
    }
}

All Problems

All Solutions