215. Kth Largest Element in an Array

Difficulty:
Related Topics:
Similar Questions:

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: