215.数组中的第K个最大元素

数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：[3,2,1,5,6,4], k = 2
输出：5

示例 2：

输入：[3,2,3,1,2,4,5,5,6], k = 4
输出：4

提示：

• 1 <= k <= nums.length <= $10^5$
• $-10^4$ <= nums[i] <= $10^4$

解析

快速选择算法（QuickSelect），基于快排的分区思想。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const target = nums.length - k; // 转为第 target 小

  function quickSelect(left, right) {
    const pivot = nums[right];
    let i = left;
    for (let j = left; j < right; j++) {
      if (nums[j] <= pivot) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
      }
    }
    [nums[i], nums[right]] = [nums[right], nums[i]];

    if (i === target) return nums[i];
    if (i < target) return quickSelect(i + 1, right);
    return quickSelect(left, i - 1);
  }

  return quickSelect(0, nums.length - 1);
};

快速选择的平均时间复杂度 O(n)，每次只递归一侧，比完整快排更高效。