力扣刷题：数组中的第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. 选择基准值：从数组中选一个元素作为基准（pivot）

2. 分区：将数组分为三部分：

   left：所有大于基准值的元素

   mid：所有等于基准值的元素

   right：所有小于基准值的元素

3. 判断目标位置：
   如果 k ≤ left.length，说明第k大的元素在left中
   如果 k > left.length 且 k ≤ left.length + mid.length，说明第k大的元素就是基准值
   否则，第k大的元素在right中

4. 递归处理：在相应的子数组中继续查找

/** * @param {number[]} nums * @param {number} k * @return {number} */varfindKthLargest=function(nums,k){if(nums.length<=1){returnnums[0]}constmidIndex=Math.floor(nums.length/2)constmideValue=nums[midIndex]constleft=[]constmid=[]constright=[]for(leti=0;i<nums.length;i++){if(mideValue<nums[i]){left.push(nums[i])}elseif(mideValue>nums[i]){right.push(nums[i])}else{mid.push(nums[i])}}if(k<=left.length){returnfindKthLargest(left,k)}elseif(k-left.length-mid.length<=0){returnmid[0]}else{returnfindKthLargest(right,k-left.length-mid.length)}};