题目描述
215. 数组中的第K个最大元素
难度中等
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
样例
示例 1:
输入: [3,2,1,5,6,4] 和
k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和
k = 4
输出: 4
说明:
你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。
算法1
(STL nth_element) $O(n)$
- 据说库函数中的
nth_element
就是用快速排序实现的,要求得第 $k$ 大的数字,就是去求第 $nums.size() - k$ 小的数字。
C++ 代码
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int p = nums.size() - k;
nth_element(nums.begin(), nums.begin() + p, nums.end());
return nums[p];
}
};
算法2
(快速选择) $O(n)$
-
套用 AcWing 786.第k个数 模板题模板。
-
写法一:在模板上稍加改动,不用求 $sl$,递归部分条件改为 $k <= j$,且将 $k$ 变化一下,如要求第 $k$ 大的数,其实就是求第$nums.size() - k$ 小的数。
- 写法二:保持原模板不变,要求第 $k$ 大的数,将$k$ 变为 $nums.size() - k + 1$
C++ 代码 写法一:
class Solution {
public:
int quick_sort(vector<int>& nums, int l, int r, int k) {
if (l == r) return nums[l];
int i = l - 1, j = r + 1, x = nums[(l + r)/2];
while (i < j)
{
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) swap(nums[i], nums[j]);
}
//差别(1)
if (k <= j) return quick_sort(nums, l, j, k);
else return quick_sort(nums, j + 1, r, k);
}
int findKthLargest(vector<int>& nums, int k) {
return quick_sort(nums, 0, nums.size() - 1, nums.size() - k); //差别(2)
}
};
C++ 代码 写法二:
class Solution {
public:
int quick_sort(vector<int>& nums, int l, int r, int k) {
if (l == r) return nums[l];
int i = l - 1, j = r + 1, x = nums[(l + r)/2];
while (i < j)
{
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) swap(nums[i], nums[j]);
}
//差别(1)
int sl = j - l + 1;
if (k <= sl) return quick_sort(nums, l, j, k);
else return quick_sort(nums, j + 1, r, k - sl);
}
int findKthLargest(vector<int>& nums, int k) {
return quick_sort(nums, 0, nums.size() - 1, nums.size() - k + 1); //差别(2)
}
};