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

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 {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickSort(nums, 0, n - 1, n - k);
    }

    private int quickSort(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        int i = left - 1, j = right + 1;
        int x = nums[(left + right) >>> 1];
        while (i < j) {
            while (nums[++i] < x)
                ;
            while (nums[--j] > x)
                ;
            if (i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        if (j < k) {
            return quickSort(nums, j + 1, right, k);
        }
        return quickSort(nums, left, j, k);
    }
}

// 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:
        lo, hi = 0, len(nums) - 1

        while lo <= hi:
            pos = self.partition(nums, lo, hi)
            if pos == k - 1: # pos starting from 0, so -1
                return nums[pos]  # partially sorted, desc
            elif pos > k - 1:
                hi = pos - 1
            else:  # pos < k - 1
                lo = pos + 1

        return -1  # or raise exception

    def partition(self, nums: List[int], lo: int, hi: int) -> int:
        pivot, l, r = nums[lo], lo + 1, hi
        while l <= r:
            if nums[l] < pivot and nums[r] > pivot:
                # larger num at left of pivot, easier to count for k-th lagest
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
            if nums[l] >= pivot:
                l += 1
            if nums[r] <= pivot:
                r -= 1
        # use nums[l] will lead to infinate looping
        nums[lo], nums[r] = nums[r], nums[lo]
        # possible there is duplicated num, but will be covered here
        return r


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

func findKthLargest(nums []int, k int) int {
	n := len(nums)
	return quickSort(nums, 0, n-1, n-k)
}

func quickSort(nums []int, left, right, k int) int {
	if left == right {
		return nums[left]
	}
	i, j := left-1, right+1
	x := nums[(left+right)>>1]
	for i < j {
		for {
			i++
			if nums[i] >= x {
				break
			}
		}
		for {
			j--
			if nums[j] <= x {
				break
			}
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	if j < k {
		return quickSort(nums, j+1, right, k)
	}
	return quickSort(nums, left, j, k)
}

function findKthLargest(nums: number[], k: number): number {
    const n = nums.length;
    const swap = (i: number, j: number) => {
        [nums[i], nums[j]] = [nums[j], nums[i]];
    };
    const sort = (l: number, r: number) => {
        if (l + 1 > k || l >= r) {
            return;
        }
        swap(l, l + Math.floor(Math.random() * (r - l)));
        const num = nums[l];
        let mark = l;
        for (let i = l + 1; i < r; i++) {
            if (nums[i] > num) {
                mark++;
                swap(i, mark);
            }
        }
        swap(l, mark);

        sort(l, mark);
        sort(mark + 1, r);
    };
    sort(0, n);
    return nums[k - 1];
}

use rand::Rng;

impl Solution {
    pub fn find_kth_largest(mut nums: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let n = nums.len();
        let mut l = 0;
        let mut r = n;
        while l <= k - 1 && l < r {
            nums.swap(l, rand::thread_rng().gen_range(l, r));
            let num = nums[l];
            let mut mark = l;
            for i in l..r {
                if nums[i] > num {
                    mark += 1;
                    nums.swap(i, mark);
                }
            }
            nums.swap(l, mark);
            if mark + 1 <= k {
                l = mark + 1;
            } else {
                r = mark;
            }
        }
        nums[k - 1]
    }
}

215 - Kth Largest Element in an Array

Question

215. Kth Largest Element in an Array

Level

Description

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

215. Kth Largest Element in an Array

Level

Description

Algorithm

Code

All Problems

All Solutions