Quick Select

Average: O(n)
Worst: O(n²)
n = size(array)

Python | Java

	def findKthLargest(self, nums: List[int], k: int) -> int:
	def qselect(nums: List[int], l: int, r: int, k: int) -> None:
	p = partition(nums, l, r)
	if p < k:
	return qselect(nums, p + 1, r, k)
	if p > k:
	return qselect(nums, l, p - 1, k)
	return nums[p]
	def partition(nums: List[int], l: int, r: int) -> int:
	pivot, p = nums[r], r
	i = l
	while i < p:
	if nums[i] > pivot:
	nums[i], nums[p - 1] = nums[p - 1], nums[i]
	nums[p], nums[p - 1] = nums[p - 1], nums[p]
	i -= 1
	p -= 1
	i += 1
	return p
	return qselect(nums, 0, len(nums) - 1, len(nums) - k)

view raw findKthLargest.py hosted with ❤ by GitHub

	public int findKthLargest(int[] nums, int k) {
	return quickSelect(nums, 0, nums.length - 1, nums.length - k);
	}
	private int quickSelect(int[] nums, int l, int r, int k) {
	int p = partition(nums, l, r);
	if (p < k) return quickSelect(nums, p + 1, r, k);
	if (p > k) return quickSelect(nums, l, p - 1, k);
	return nums[p];
	}
	private int partition(int[] nums, int l, int r) {
	int pivot = nums[r];
	int p = r;
	for (int i = l; i < p; i++) {
	if (nums[i] > pivot) {
	swap(nums, i, p - 1);
	swap(nums, p, p - 1);
	i--;
	p--;
	}
	}
	return p;
	}
	private void swap(int[] nums, int a, int b) {
	int tmp = nums[a];
	nums[a] = nums[b];
	nums[b] = tmp;
	}

view raw FindKthLargest.java hosted with ❤ by GitHub

Tricks

Quick Select