【算法】数组中的第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个元素，而无需完全排序数组。
- 选择基准：从数组中随机选择一个元素作为基准元素，或者选择数组的第一个元素、最后一个元素等作为基准。
- 分区操作：将数组分为两部分，一部分包含所有不大于基准的元素，另一部分包含所有大于基准的元素。这个操作结束后，基准元素会处于它在排序后数组中的最终位置。同时，我们也会得到基准元素在排序后数组中的索引。
- 根据基准索引判断：
- 如果基准元素的索引正好是k-1，那么基准元素就是我们要找的第k大的元素。
- 如果基准元素的索引小于k-1，说明第k大的元素在基准的右边，我们在基准的右边数组中继续执行前两步。
- 如果基准元素的索引大于k-1，说明第k大的元素在基准的左边，我们在基准的左边数组中继续执行前两步。
- 递归或迭代：重复上述过程，直到找到第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）！