215. Kth Largest Element in an Array

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
/**
 * 解题思路：快速选择（QuickSelect）算法
 * 核心思想：基于快速排序的分治思想，不需要完全排序数组，只需找到第k大的元素
 * 时间复杂度：平均O(n)，最坏O(n²)（随机选基准可降低最坏情况概率）
 * 空间复杂度：O(n)（递归栈+分区数组）
 */

function findKthLargest(nums, k) {
  /**
   * 快速选择核心函数
   * @param {number[]} nums - 当前要处理的子数组
   * @param {number} k - 要找的第k大元素
   * @returns {number} 找到的目标元素
   */
  const quickSelect = (nums, k) => {
    // 1. 随机选择基准值（pivot），避免有序数组导致的最坏情况
    const pivotIndex = Math.floor(Math.random() * nums.length)
    const pivot = nums[pivotIndex]

    // 2. 分区：将元素分为大于、等于、小于pivot的三组
    const big = [] // 存储大于pivot的元素
    const equal = [] // 存储等于pivot的元素
    const small = [] // 存储小于pivot的元素

    for (const num of nums) {
      if (num > pivot) {
        big.push(num)
      } else if (num < pivot) {
        small.push(num)
      } else {
        equal.push(num)
      }
    }

    // 3. 递归/返回判断
    // 情况1：第k大元素在big数组中，直接递归处理big数组
    if (k <= big.length) {
      return quickSelect(big, k)
    }
    // 情况2：第k大元素在small数组中
    // 计算在small数组中要找的新k值：k - (big.length + equal.length)
    else if (k > big.length + equal.length) {
      return quickSelect(small, k - big.length - equal.length)
    }
    // 情况3：第k大元素在equal数组中，直接返回pivot即可
    else {
      return pivot
    }
  }

  // 调用快速选择函数并返回结果
  return quickSelect(nums, k)
}