algorithms►leetcode

032-数组中第k个最大元素(计数排序)

215. 数组中的第K个最大元素-Medium

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

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

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

示例 :

输入: [3,2,1,5,6,4], k = 2
输出: 5

第一版题解，直接用sort()

JavaScript 的 Array.prototype.sort() 方法的时间复杂度 取决于具体 JavaScript 引擎的实现，但所有现代引擎都采用 O(n log n) 时间复杂度的排序算法。

再细看一下题目要求发现超出了时间复杂度要求，虽然我觉得用原生的最简洁也更好交付。

1
2
3
4
5
6
7
8
9
10
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    //从大到小对nums排序
    const sortedNums = nums.sort((a,b)=>b-a);
    return sortedNums[k-1];
};

第二版方法 ：计数排序Counting Sort 适用于有限范围整数

时间复杂度：O(n + m)，其中 m 是数据范围（若 m 远大于 n，则可能退化为 O(n²)）
适用条件：

  • 数据范围较小（如 0 ≤ nums[i] ≤ 10000）。
  • 数据是整数（浮点数不适用）。

JavaScript 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function findKthLargest(nums, k) {
    const min = Math.min(...nums);
    const max = Math.max(...nums);
    const count = Array(max - min + 1).fill(0);
    
    for (const num of nums) {
        count[num - min]++;
    }
    
    let sum = 0;
    for (let i = count.length - 1; i >= 0; i--) {
        sum += count[i];
        if (sum >= k) {
            //将计数数组的索引i转换为原始数组中的真实数值并返回
            return i + min;
        }
    }
    return -1;
}

适用场景：

  • 如果数据范围 max - min 较小（如 1 ≤ nums[i] ≤ 10000），则 **O(n + m) ≈ O(n)**。
  • 但如果 nums = [1, 1000000]，则 m = 1000000，此时 **O(n + m) 退化为 O(m)**，不满足要求。