Mr.He

Mr.He大约 3 分钟

/**

* @param {number[]} nums

* @param {number} k

* @return {number}

*/

var findKthLargest = function(nums, k) {
	// 如果不使用 sort 参数，默认是按照转成字符串来排序
	return nums.sort((a, b) => a-b)[nums.length-k]

};

这道题要求在 $O(n)$ 时间复杂度内找到数组中第 $k$ 个最大的元素。最经典的方法是使用 快速选择算法。快速选择算法是快速排序的变种。它的核心思想是：

随机选择一个基准值。
根据基准值将数组分为两部分：比基准值大的放在左边，比基准值小的放在右边（因为我们要找第 $k$ 大，所以把大的放左边更方便索引）。
判断基准值最终的位置索引：
- 如果索引等于 $k-1$，说明该基准值就是第 $k$ 大的元素，直接返回。
- 如果索引大于 $k-1$，说明目标在左半部分，递归左边。
- 如果索引小于 $k-1$，说明目标在右半部分，递归右边。以下是 JavaScript 的实现代码：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    // 快速选择算法
    const quickSelect = (left, right) => {
        // 1. 随机选择基准值索引，避免最坏情况（如数组已排序）
        const pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
        const pivotValue = nums[pivotIndex];
        
        // 2. 将基准值交换到最右侧
        [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];
        
        // 3. 分区操作
        // i 指向下一个将要放置比基准值大的元素的位置
        let i = left;
        for (let j = left; j < right; j++) {
            // 我们要找第 k 大，所以按降序排列：大的放左边
            if (nums[j] > pivotValue) {
                [nums[i], nums[j]] = [nums[j], nums[i]];
                i++;
            }
        }
        
        // 4. 将基准值归位到正确位置 i
        // 此时 nums[left...i-1] 都大于 pivotValue
        // nums[i+1...right] 都小于等于 pivotValue
        [nums[i], nums[right]] = [nums[right], nums[i]];
        
        // 5. 判断基准值的位置
        // 第 k 大的元素在降序排列中的索引是 k - 1
        if (i === k - 1) {
            return nums[i];
        } else if (i > k - 1) {
            // 目标在左侧部分
            return quickSelect(left, i - 1);
        } else {
            // 目标在右侧部分
            return quickSelect(i + 1, right);
        }
    };
    
    return quickSelect(0, nums.length - 1);
};

复杂度分析

时间复杂度: $O(n)$。
- 快速选择的平均时间复杂度为 $O(n)$。每次分区后，我们只需要处理一边的数据。
- 推导过程类似于 $T(n) = T(n/2) + O(n)$，解为 $O(n)$。
- 虽然最坏情况（每次只排除一个元素）是 $O(n^2)$，但通过随机选择基准值，可以极大概率避免这种情况，使其平均性能非常稳定。
空间复杂度: $O(\log n)$。
- 这是递归调用栈的平均深度。最坏情况下为 $O(n)$，但平均为 $O(\log n)$。

示例解析

以输入 [3,2,1,5,6,4], k = 2 为例：

假设随机选到了 3 作为基准值。
分区后，比 3 大的 5, 6, 4 会被移到左边。数组可能变为 [5, 6, 4, 3, 2, 1]（具体顺序取决于分区逻辑，这里 3 在索引 3 的位置）。
我们要找第 2 大的元素（索引 k-1 = 1）。
基准值索引 3 大于 1，说明第 2 大的元素在左边部分 [5, 6, 4] 中。
对 [5, 6, 4] 再次进行快速选择，直到基准值落在索引 1 上，返回该值。最终答案为 5。

# 复杂度分析

# 示例解析

复杂度分析

示例解析