建湖专业做网站的公司,wordpress md主题,网站开发报告,wordpress交流论坛难度#xff1a;中等
题目#xff1a;
给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。 请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题…难度中等
题目
给定整数数组 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。
