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} */ var findKthLargest = function(nums, k) { var n = nums.length; // Kth largest element is the n - k + 1 smallest element. // n - k for index. return findRank(nums, n - k, 0, n - 1); }; var findRank = function(nums, r, left, right) { if (left === right) return nums[left]; var pivot = Math.floor(Math.random() * (right - left + 1)) + left; var 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); }; var getPivot = function(pivot, nums, left, right) { swap(nums, pivot, right); var index = left; for (let i = left; i <= right; i++) { if (nums[i] < nums[right]) { swap(nums, i, index++); } } swap(nums, index, right); return index; } var swap = function(arr, x, y) { var temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } console.log(findKthLargest([7,6,5,1,2,3,4], 5));
Output
3