Kth largest element in an array can be determined using the “Quickselect Algorithm”.
Average performance O(n)
Worst-case performance O(n^2)
/** * @param {number[]} nums * @param {number} k * @return {number} */ const findKthLargest = function(nums, k) { const n = nums.length; return findRank(nums, n - k, 0, n - 1); }; const findRank = (nums, r, left, right) => { if (left === right) return nums[left]; const pivot = Math.floor(Math.random() * (right - left + 1)) + left; const leftEnd = getPivot(pivot, nums, left, right); if (leftEnd === r) return nums[leftEnd]; else if (r < leftEnd) { return findRank(nums, r, left, leftEnd - 1); } return findRank(nums, r, leftEnd + 1, right); }; const getPivot = (pivot, nums, left, right) => { swap(nums, pivot, right); let index = left; for (let i = left; i <= right; i++) { if (nums[i] < nums[right]) { swap(nums, i, index++); } } swap(nums, index, right); return index; }; const swap = function(arr, x, y) { const temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } console.log(findKthLargest([7, 6, 5, 1, 2, 3, 4], 5));
Output
3