/*
 * @lc app=leetcode.cn id=215 lang=javascript
 *
 * [215] 数组中的第K个最大元素
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const numsCopy = [...nums];
  return quickSelect(numsCopy, 0, numsCopy.length - 1, k);
};

function quickSelect(nums, left, right, k) {
  if (left === right) {
    return nums[left];
  }
  // 随机选择pivot索引
  const pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
  [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]]; // 交换pivot到末尾
  const p = partition(nums, left, right);
  const count = p - left + 1;
  if (count === k) {
    return nums[p];
  } else if (count > k) {
    return quickSelect(nums, left, p - 1, k);
  } else {
    return quickSelect(nums, p + 1, right, k - count);
  }
}

function partition(nums, left, right) {
  const pivot = nums[right];
  let i = left;
  for (let j = left; j < right; j++) {
    if (nums[j] >= pivot) { // 将大于等于pivot的元素移到左边
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  [nums[i], nums[right]] = [nums[right], nums[i]]; // 将pivot放到正确位置
  return i;
}
// @lc code=end

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)) // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) // 4