【 每天学习一点算法 2026/03/23】数组中的第K个最大元素

每天学习一点算法 2026/03/23

题目：数组中的第K个最大元素

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

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

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

1. 最简单的方法就是先排序然后取第 k - 1 个元素

   functionfindKthLargest(nums:number[],k:number):number{returnnums.sort((a,b)=>b-a)[k-1]};

2. 上面的方法取决于排序算法的时间复杂度肯定不是我们想要的，我们可以利用快速排序方法来解决这个问题

   快速排序的关键在于选取一个基准值，然后将 大于 和 小于 基准值数放在两个数组中，然后在递归传递这两个数组，继续选取基准值分割，直到完成排序。

   • 假如 基准值 左边元素个数小于 k - 1，那么需要在右边的数组中寻找新的基准值
   • 假如 基准值 左边元素个数大于 k - 1，那么需要在左边的数组中寻找新的基准值
   • 假如 基准值 左边刚好有 k - 1 元素，那么这个基准值就是第 k 大的元素

   functionfindKthLargest(nums:number[],k:number):number{if(nums.length===1)returnnums[0];// 只有一项直接返回constbase=nums[Math.floor(Math.random()*nums.length)];// 随机基准值constleft:number[]=[]constright:number[]=[]constequal:number[]=[]// 利用基准值分割数组for(constitemofnums){if(item<base){right.push(item)}elseif(item>base){left.push(item)}else{equal.push(item)}}if(left.length===k-1){// 值大于 base 的值刚好有 k - 1 个，那么 base 就是第 k 大的元素returnbase}elseif(left.length>k-1){// 值大于 base 的值大于 k - 1 个, 那么第 k 大的元素在 left 内returnfindKthLargest(left,k)}else{// 值大于 base 的值小于 k - 1 个if(left.length+equal.length>=k){// 值在 equal 内直接返回 basereturnbase}else{// 值在 right 内（k 值记得要减去 equal 的长度）returnfindKthLargest(right,k-left.length-equal.length)}}};

3. 因为题目中数字有边界-10000 <= nums[i] <= 10000，所以我们可以利用计数排序的方法来寻找。

   functionfindKthLargest(nums:number[],k:number):number{constarr=newArray(20001).fill(0)// 用于统计数字频率constoffset=10000// 因为有负数我们添加一个偏移量for(letnumofnums){// 将数字转换成arr数字的下标，对应元素表示出现频次arr[num+offset]++}for(leti=20001;i>=0;i--){// 遍历 arr 数组if(arr[i]>0){// 如果遇到出现的数字，就用 k 减去出现的频次k-=arr[i]}if(k<=0){// k 小于等 0 表示这就是第 k 大的数字returni-offset}}};

题目来源：力扣（LeetCode）