数组中的第 K 个最大元素（LeetCode215）-Fonda's Lab

数组中的第 K 个最大元素（LeetCode215）

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

问题描述

需要找到排序后数组中的第 k 个最大的元素，而不是第 k 个不同的元素。要求设计并实现时间复杂度为 O(n) 的算法解决此问题。

方法1：快速选择算法（Quickselect）

快速选择算法是快速排序的一种变体，能够在平均情况下达到 O(n) 的时间复杂度。其核心思想是基于快速排序的分区思想，通过一次分区将数组分为两部分，然后判断第 k 大元素在哪一部分，递归或迭代进行选择。

实现步骤：

随机选择一个基准元素，并将数组分为大于和小于基准的两部分。
判断基准元素的位置与 k 的关系。
递归或迭代在适当的部分继续查找，直到找到第 k 大的元素。

代码实现：

const findKthLargest = function(nums, k) {
    const partition = (left, right) => {
        const pivot = nums[right];
        let pIndex = left;
        for (let i = left; i < right; i++) {
            if (nums[i] >= pivot) {
                [nums[i], nums[pIndex]] = [nums[pIndex], nums[i]];
                pIndex++;
            }
        }
        [nums[pIndex], nums[right]] = [nums[right], nums[pIndex]];
        return pIndex;
    };

    let left = 0, right = nums.length - 1, index = nums.length - k;
    while (left <= right) {
        const pivotIndex = partition(left, right);
        if (pivotIndex === index) {
            return nums[pivotIndex];
        } else if (pivotIndex < index) {
            left = pivotIndex + 1;
        } else {
            right = pivotIndex - 1;
        }
    }
};

方法2：最小堆

最小堆是一种完全二叉树，堆中每个节点的值都小于或等于其子节点的值。通过维护一个大小为 k 的最小堆，可以确保堆顶元素始终是当前最大的 k 个元素中的最小值。

实现步骤：

构建最小堆：使用数组实现最小堆。
遍历数组：将每个元素添加到最小堆中。
保持堆的大小为 k：如果堆的大小超过 k，则删除堆顶元素（最小元素）。
返回堆顶元素：遍历结束后，堆顶元素即为第 k 大的元素。

class MinHeap {
    constructor() {
        this.heap = [];
    }

    size() {
        return this.heap.length;
    }

    peek() {
        return this.heap[0];
    }

    insert(value) {
        this.heap.push(value);
        this.heapifyUp();
    }

    remove() {
        if (this.size() === 1) {
            return this.heap.pop();
        }
        const root = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return root;
    }

    heapifyUp() {
        let index = this.size() - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] <= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    heapifyDown() {
        let index = 0;
        const length = this.size();
        const element = this.heap[0];
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild < element) {
                    swap = leftChildIndex;
                }
            }

            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if ((swap === null && rightChild < element) || (swap !== null && rightChild < leftChild)) {
                    swap = rightChildIndex;
                }
            }

            if (swap === null) break;
            [this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
            index = swap;
        }
    }
}

const findKthLargest = function(nums, k) {
    const minHeap = new MinHeap();
  
    for (let num of nums) {
        minHeap.insert(num);
        if (minHeap.size() > k) {
            minHeap.remove();
        }
    }
  
    return minHeap.peek();
};

// 示例测试
console.log(findKthLargest([3,2,1,5,6,4], 2)); // 输出: 5
console.log(findKthLargest([3,2,3,1,2,4,5,5,6], 4)); // 输出: 4

方法3：库函数

使用 JavaScript 的内置排序方法 Array.sort 和 slice 进行排序和切片，直接返回第 k 大的元素。虽然这种方法简单，但时间复杂度为 O(n log n)，不满足题目要求的 O(n)。

代码实现：

const findKthLargest = function(nums, k) {
    nums.sort((a, b) => b - a);
    return nums[k - 1];
};

总结

本文介绍了三种方法来解决数组中的第 k 个最大元素问题：快速选择算法、最小堆和库函数。快速选择算法和最小堆都能在平均情况下达到 O(n) 的时间复杂度，而使用库函数的排序方法虽然简单，但时间复杂度为 O(n log n)。根据具体需求选择合适的方法进行实现。

目录CONTENT

数组中的第 K 个最大元素（LeetCode215）