215.数组中的第 k 个最大元素

排序

最简单的方法是对数组进行排序，然后直接返回第 K 个最大的元素。

代码实现

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    nums.sort((a, b) => b - a);
    return nums[k - 1];
};

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

选择排序

details

var findKthLargest = function (nums, k) {
    //边界值处理
    if (nums.length <= 1) return nums[k - 1];
    //

    let i = 0;
    let temp = 0;
    while (i < nums.length) {
        let j = i;
        let maxIndex = i;

        while (j < nums.length) {
            if (nums[j] > nums[maxIndex]) {
                maxIndex = j;
            }
            j++;
        }

        // 交换i跟最大的元素
        if (i !== maxIndex) {
            temp = nums[i];
            nums[i] = nums[maxIndex];
            nums[maxIndex] = temp;
        }
        // console.log(JSON.stringify(nums), i, j, nums[maxIndex]);
        // 找到第K 个就结束了
        if (i >= k - 1) {
            return nums[k - 1];
        }
        i++;
    }
    return nums[k];
};

使用最小堆

可以使用最小堆来维护数组中最大的 K 个元素。这样堆顶元素就是第 K 个最大的元素。

代码实现

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

    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop() {
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.bubbleDown(0);
        }
        return min;
    }

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

    bubbleUp(index) {
        const element = this.heap[index];
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];
            if (element >= parent) break;
            this.heap[index] = parent;
            index = parentIndex;
        }
        this.heap[index] = element;
    }

    bubbleDown(index) {
        const length = this.heap.length;
        const element = this.heap[index];
        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];
            index = swap;
        }
        this.heap[index] = element;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    const minHeap = new MinHeap();
    for (let num of nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    return minHeap.pop();
};

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

快速选择算法

快速选择算法类似于快速排序，通过分区操作来查找第 K 个最大的元素。

代码实现

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    const n = nums.length;
    return quickSelect(nums, 0, n - 1, n - k);
};

function quickSelect(arr, left, right, k) {
    if (left === right) return arr[left];

    let pivotIndex = partition(arr, left, right);
    if (k === pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k);
    }
}

function partition(arr, left, right) {
    let pivot = arr[right];
    let pivotIndex = left;

    for (let i = left; i < right; i++) {
        if (arr[i] <= pivot) {
            [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
            pivotIndex++;
        }
    }
    [arr[pivotIndex], arr[right]] = [arr[right], arr[pivotIndex]];
    return pivotIndex;
}

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

总结

• 排序方法 时间复杂度为 $O(n \log n)$，适用于简单情况。
• 堆方法 时间复杂度为 $O(n \log k)$，适用于处理大数据流。
• 快速选择算法 时间复杂度为 $O(n)$ 平均情况，最坏情况为 $O(n^2)$，适用于需要高效处理的情况。