Welcome to Subscribe On Youtube

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--); // larger num at left of pivot, easier to count for k-th lagest
                }
                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();
        }
    }
}

  • // https://leetcode.com/problems/kth-largest-element-in-an-array/
// Time: O(N + klogN)
// Space: O(1)
class Solution {
    void siftDown(vector<int> &A, int end, int index) {
        if (index < 0 || index >= end) return;
        int child = 2 * index + 1;
        while (child < end) {
            if (child + 1 < end && A[child + 1] > A[child]) ++child;
            if (A[index] > A[child]) break;
            swap(A[index], A[child]);
            index = child;
            child = 2 * index + 1;
        }
    }
    void heapify(vector<int> &A) {
        for (int i = A.size() / 2 - 1; i >= 0; --i) siftDown(A, A.size(), i);
    }
public:
    int findKthLargest(vector<int>& A, int k) {
        heapify(A);
        int N = A.size();
        for (int i = 1; i < k; ++i) {
            swap(A[0], A[N - 1]);
            --N;
            siftDown(A, N, 0);
        }
        return A[0];
    }
};

  • class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_sort(left, right, k):
            if left == right:
                return nums[left]
            i, j = left - 1, right + 1
            x = nums[(left + right) >> 1]
            while i < j:
                while 1:
                    i += 1
                    if nums[i] >= x:
                        break
                while 1:
                    j -= 1
                    if nums[j] <= x:
                        break
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            if j < k:
                return quick_sort(j + 1, right, k)
            return quick_sort(left, j, k)

        n = len(nums)
        return quick_sort(0, n - 1, n - k)

############

import random


class Solution(object):
  def findKthLargest(self, nums, k):
    """
    :type A: List[int]
    :type k: int
    :rtype: int
    """

    def quickselect(start, end, nums, k):
      if start == end:
        return nums[start]

      mid = partition(start, end, nums)

      if mid == k:
        return nums[mid]
      elif k > mid:
        return quickselect(mid + 1, end, nums, k)
      else:
        return quickselect(start, mid - 1, nums, k)

    def partition(start, end, nums):
      p = random.randrange(start, end + 1)
      pv = nums[p]
      nums[end], nums[p] = nums[p], nums[end]
      mid = start
      for i in range(start, end):
        if nums[i] >= pv:
          nums[i], nums[mid] = nums[mid], nums[i]
          mid += 1
      nums[mid], nums[end] = nums[end], nums[mid]
      return mid

    ret = quickselect(0, len(nums) - 1, nums, k - 1)
    return ret

  def partition(start, end, nums):
    p = random.randrange(start, end + 1)
    pv = nums[p]
    nums[end], nums[p] = nums[p], nums[end]
    mid = start
    for i in range(start, end):
      if nums[i] >= pv:
        nums[i], nums[mid] = nums[mid], nums[i]
        mid += 1
    nums[mid], nums[end] = nums[end], nums[mid]
    return mid

All Problems

All Solutions