Problem
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.
Solution
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
return quickSelect(nums, 0, nums.length - 1, k);
};
var quickSelect = function (nums, left, right, k) {
var le = left;
var ri = right;
var mid = nums[right];
while (le < ri) {
if (nums[le++] > mid) swap(nums, --le, --ri);
}
swap(nums, le, right);
var len = right - le;
if (len === k - 1) return nums[le];
else if (len < k - 1) return quickSelect(nums, left, le - 1, k - len - 1);
else return quickSelect(nums, le + 1, right, k);
};
var swap = function (nums, i, j) {
var tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).