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

每天学习一点算法 2026/03/23题目数组中的第K个最大元素给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。最简单的方法就是先排序然后取第 k - 1 个元素functionfindKthLargest(nums:number[],k:number):number{returnnums.sort((a,b)b-a)[k-1]};上面的方法取决于排序算法的时间复杂度肯定不是我们想要的我们可以利用快速排序方法来解决这个问题快速排序的关键在于选取一个基准值然后将 大于 和 小于 基准值数放在两个数组中然后在递归传递这两个数组继续选取基准值分割直到完成排序。假如 基准值 左边元素个数小于 k - 1那么需要在右边的数组中寻找新的基准值假如 基准值 左边元素个数大于 k - 1那么需要在左边的数组中寻找新的基准值假如 基准值 左边刚好有 k - 1 元素那么这个基准值就是第 k 大的元素functionfindKthLargest(nums:number[],k:number):number{if(nums.length1)returnnums[0];// 只有一项直接返回constbasenums[Math.floor(Math.random()*nums.length)];// 随机基准值constleft:number[][]constright:number[][]constequal:number[][]// 利用基准值分割数组for(constitemofnums){if(itembase){right.push(item)}elseif(itembase){left.push(item)}else{equal.push(item)}}if(left.lengthk-1){// 值大于 base 的值刚好有 k - 1 个那么 base 就是第 k 大的元素returnbase}elseif(left.lengthk-1){// 值大于 base 的值大于 k - 1 个, 那么第 k 大的元素在 left 内returnfindKthLargest(left,k)}else{// 值大于 base 的值小于 k - 1 个if(left.lengthequal.lengthk){// 值在 equal 内直接返回 basereturnbase}else{// 值在 right 内k 值记得要减去 equal 的长度returnfindKthLargest(right,k-left.length-equal.length)}}};因为题目中数字有边界-10000 nums[i] 10000所以我们可以利用计数排序的方法来寻找。functionfindKthLargest(nums:number[],k:number):number{constarrnewArray(20001).fill(0)// 用于统计数字频率constoffset10000// 因为有负数我们添加一个偏移量for(letnumofnums){// 将数字转换成arr数字的下标对应元素表示出现频次arr[numoffset]}for(leti20001;i0;i--){// 遍历 arr 数组if(arr[i]0){// 如果遇到出现的数字就用 k 减去出现的频次k-arr[i]}if(k0){// k 小于等 0 表示这就是第 k 大的数字returni-offset}}};题目来源力扣LeetCode