hot100 堆

打算在这系列博客把hot100的题扫一遍，分模块来。

数组中的第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 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

思路：

这题的o(n)挺难想到的，如果要考虑排序，最快的排序的时间复杂度也是o(nlogn)。因此参照了灵神的思路。

215. 数组中的第K个最大元素 - 力扣（LeetCode）

选第k大的元素的典型思路显然是堆，不过这题的时间复杂度是o(n)，堆排序也是做不到的，除非这题都是定制数据。

堆排序的maxHeapify是基于数组的典型建堆思路，需要掌握。

代码：

快选：

// 在子数组 [left, right] 中随机选择一个基准元素 pivot
// 根据 pivot 重新排列子数组 [left, right]
// 重新排列后，<= pivot 的元素都在 pivot 的左侧，>= pivot 的元素都在 pivot 的右侧
// 返回 pivot 在重新排列后的 nums 中的下标
// 特别地，如果子数组的所有元素都等于 pivot，我们会返回子数组的中心下标，避免退化
function partition(nums, left, right) {
    // 1. 在子数组 [left, right] 中随机选择一个基准元素 pivot
    const idx = left + Math.floor(Math.random() * (right - left + 1));
    const pivot = nums[idx];
    // 把 pivot 与子数组第一个元素交换，避免 pivot 干扰后续划分，从而简化实现逻辑
    [nums[idx], nums[left]] = [nums[left], nums[idx]];

    // 2. 相向双指针遍历子数组 [left + 1, right]
    // 循环不变量：在循环过程中，子数组的数据分布始终如下图
    // [ pivot | <=pivot | 尚未遍历 | >=pivot ]
    //   ^                 ^     ^         ^
    //   left              i     j         right

    let i = left + 1, j = right;
    while (true) {
        while (i <= j && nums[i] < pivot) {
            i++;
        }
        // 此时 nums[i] >= pivot

        while (i <= j && nums[j] > pivot) {
            j--;
        }
        // 此时 nums[j] <= pivot

        if (i >= j) {
            break;
        }

        // 维持循环不变量
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
        j--;
    }

    // 循环结束后
    // [ pivot | <=pivot | >=pivot ]
    //   ^             ^   ^     ^
    //   left          j   i     right

    // 3. 把 pivot 与 nums[j] 交换，完成划分（partition）
    // 为什么与 j 交换？
    // 如果与 i 交换，可能会出现 i = right + 1 的情况，已经下标越界了，无法交换
    // 另一个原因是如果 nums[i] > pivot，交换会导致一个大于 pivot 的数出现在子数组最左边，不是有效划分
    // 与 j 交换，即使 j = left，交换也不会出错
    [nums[left], nums[j]] = [nums[j], nums[left]];

    // 返回 pivot 的下标
    return j;
}

var findKthLargest = function(nums, k) {
    const n = nums.length;
    const targetIndex = n - k; // 第 k 大元素在升序数组中的下标是 n - k
    let left = 0, right = n - 1; // 闭区间
    while (true) {
        const i = partition(nums, left, right);
        if (i === targetIndex) {
            // 找到第 k 大元素
            return nums[i];
        }
        if (i > targetIndex) {
            // 第 k 大元素在 [left, i - 1] 中
            right = i - 1;
        } else {
            // 第 k 大元素在 [i + 1, right] 中
            left = i + 1;
        }
    }
};

堆排序，虽然o(nlogn)，但是定制题目，也能过：

var findKthLargest = function(nums, k) {
    let heapSize = nums.length;

    // 将以i为根的子树调整为大顶堆
    // 逻辑：找i和其左右子中最大的，如果i不是最大的就交换，然后继续往下调整
    function maxHeapify(i) {
        const l = i * 2 + 1, r = i * 2 + 2; // 左子、右子下标
        let largest = i; // 先假设自己最大

        // 左子存在且比当前最大值大 → 更新largest
        if (l < heapSize && nums[l] > nums[largest]) largest = l;
        // 右子存在且比当前最大值大 → 更新largest
        if (r < heapSize && nums[r] > nums[largest]) largest = r;

        // 如果有子节点比父节点大，交换并继续往下调整
        if (largest !== i) {
            [nums[i], nums[largest]] = [nums[largest], nums[i]];
            maxHeapify(largest); // 换下去的可能破坏子树，递归修复
        }
    }

    // 建堆：从最后一个非叶子节点往根的方向，逐个执行maxHeapify
    // heapSize/2-1 开始？因为后面的都是叶子节点，没有子树不需要调整
    // 为什么从后往前？因为要先让底层子树满足堆性质，才能调整上层的父节点
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
    	maxHeapify(i);
    }

    // 弹出k-1个最大值，剩下的堆顶就是第k大
    // 每次把堆顶（最大值）和末尾交换，heapSize--相当于"删除"它
    for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
        [nums[0], nums[i]] = [nums[i], nums[0]]; // 堆顶最大值换到末尾
        heapSize--; // 缩小堆的范围，末尾元素"出堆"
        maxHeapify(0); // 重新调整堆顶
    }

    // 堆顶就是第k大的元素
    return nums[0];
};