【算法】数组中的第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

解题思路：

要找到数组中第k个最大的元素，且要求时间复杂度为O(n)，我们可以使用快速选择算法，这是一种基于快速排序的选择算法变种，用于找到未排序数组中的第k个元素，而无需完全排序数组。

1. 选择基准：从数组中随机选择一个元素作为基准元素，或者选择数组的第一个元素、最后一个元素等作为基准。
2. 分区操作：将数组分为两部分，一部分包含所有不大于基准的元素，另一部分包含所有大于基准的元素。这个操作结束后，基准元素会处于它在排序后数组中的最终位置。同时，我们也会得到基准元素在排序后数组中的索引。
3. 根据基准索引判断：

• 如果基准元素的索引正好是k-1，那么基准元素就是我们要找的第k大的元素。
• 如果基准元素的索引小于k-1，说明第k大的元素在基准的右边，我们在基准的右边数组中继续执行前两步。
• 如果基准元素的索引大于k-1，说明第k大的元素在基准的左边，我们在基准的左边数组中继续执行前两步。

4. 递归或迭代：重复上述过程，直到找到第k大的元素。

JavaScript实现：

function findKthLargest(nums, k) {
    function partition(left, right, pivotIndex) {
        const pivotValue = nums[pivotIndex];
        // 将基准元素交换到数组末尾
        [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];
        let storeIndex = left;
        for (let i = left; i < right; i++) {
            if (nums[i] > pivotValue) {
                [nums[storeIndex], nums[i]] = [nums[i], nums[storeIndex]];
                storeIndex++;
            }
        }
        // 将基准元素放到正确的位置
        [nums[right], nums[storeIndex]] = [nums[storeIndex], nums[right]];
        return storeIndex;
    }

    function quickSelect(left, right, kSmallest) {
        if (left === right) return nums[left];

        let pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
        pivotIndex = partition(left, right, pivotIndex);

        if (kSmallest === pivotIndex) {
            return nums[kSmallest];
        } else if (kSmallest < pivotIndex) {
            return quickSelect(left, pivotIndex - 1, kSmallest);
        } else {
            return quickSelect(pivotIndex + 1, right, kSmallest);
        }
    }

    // 调整k为基于0的索引
    return quickSelect(0, nums.length - 1, nums.length - k);
}

// 示例
console.log(findKthLargest([3,2,1,5,6,4], 2)); // 输出: 5，因为排序后数组为[1,2,3,4,5,6]，第2大的元素是5

这段代码首先定义了partition函数来实现分区操作，然后定义了quickSelect函数来递归地执行快速选择算法。最后，findKthLargest函数调用quickSelect来找到数组中第k大的元素。注意，由于我们是从0开始计数，所以在调用quickSelect时传入的是nums.length - k。

原文地址：https://blog.csdn.net/xiaolinlife/article/details/140535173

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！