leetcode 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
题目
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例：
输入: [3,2,1,5,6,4] 和 k = 2输出: 5
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
解答& 代码
解法一：先排序
快速排序参考：快速排序 - 菜鸟教程，时间复杂度 O(Nlog(N))
- 先将数组从大到小排序
取第 k-1 个数
class Solution { private: // 快排，将数组 num 的下标 left 到 right 的元素排序（包含 left 和 right） void QuickSort(vector<int>& num, int left, int right) { if(left < right) { // 随机选择第 randIdx 个数作为基准数 int randIdx = rand() % (right - left + 1) + left; swap(num[randIdx], num[left]); // 将这个基准数交换到数组最左边 left 的位置 int i = left; // 用于从左往右找 int j = right; // 用于从右往左找 int x = num[left]; // 基准数 while(i < j) { while(i < j && num[j] <= x) // 从右往左找第一个比基准数 x 大的数 --j; if(i < j) { num[i] = num[j]; // 将这个数填到左边的坑 num[i] 中 ++i; } while(i < j && num[i] >= x) // 从左往右找第一个比基准数 x 小的数 ++i; if(i < j) { num[j] = num[i]; // 将这个数填到右边的坑 num[j] 中 --j; } } num[i] = x; // 将基准数放置到正确的位置，其左边的数都比它大，右边的数都比它小 QuickSort(num, left, i - 1); // 递归对基准数左边部分进行排序 QuickSort(num, i + 1, right); // 递归对基准数右边部分进行排序 } } // 从大到小排序 void sort(vector<int>& nums) { QuickSort(nums, 0, nums.size() - 1); } public: int findKthLargest(vector<int>& nums, int k) { sort(nums); // 排序 return nums[k - 1]; // 取第 k 大的元素，因为下标是从 0 开始，所以取第 k-1 个元素 } };删除第 8-10 行代码，即每次将最左边的元素作为基准数的执行结果： ``` 执行结果：通过
执行用时：192 ms, 在所有 C++ 提交中击败了 7.58% 的用户 内存消耗：10 MB, 在所有 C++ 提交中击败了 9.75% 的用户
加了第 8-10 行代码，随机选择基准数后，执行结果变好了：
执行结果：通过
执行用时：12 ms, 在所有 C++ 提交中击败了 60.95% 的用户 内存消耗：9.8 MB, 在所有 C++ 提交中击败了 52.28% 的用户
<a name="rkdKs"></a>
## 解法二：快速选择（O(N)）
使用快排从大到小排序，但不需要进行完整排序。快排过程中，
- 如果分区时基准元素最终的位置为 k-1，那么这个基准元素就是第 k 大的元素，不用继续排序，直接返回
- 如果分区时基准元素最终的位置大于 k-1，那么第 k 大的元素在其左半边，只需排序左半边
- 如果分区时基准元素最终的位置小于 k-1，那么第 k 大的元素在其右半边，只需排序右半边
- 时间复杂度：**O(n)**，参考「《算法导论》9.2：期望为线性的选择算法」
- 注意：**快速排序的期望运行时间为 O(nlogn)，但快速选择的期望运行时间为 O(n)**
- 粗略估计：假设每次选取的基准元素位置正好都在区间的中间位置，那么恰好能排除一半的元素，那么第一次调用 partition 时需要遍历 n 个元素，第二次调用 partition 时需要 n/2 个元素... ... 那么 T(n) = n + n/2 + n/4 + ... < 2n，因此时间复杂度为 O(n)
- 空间复杂度：O(logn)，递归使用的栈空间
```cpp
class Solution {
private:
// 快排分割函数
int partition(vector<int>& nums, int left, int right)
{
int randomIdx = rand() % (right - left + 1) + left;
swap(nums[left], nums[randomIdx]);
int pivot = nums[left];
while(left < right)
{
while(left < right && nums[right] <= pivot)
--right;
nums[left] = nums[right];
while(left < right && nums[left] >= pivot)
++left;
nums[right] = nums[left];
}
nums[left] = pivot;
return left;
}
// 快排主函数（从大到小排序）
void quickSort(vector<int>& nums, int left, int right, int k)
{
if(left >= right)
return;
int pivot = partition(nums, left, right);
if(pivot == k - 1) // 如果基准元素最终被排序到第 k-1 个位置，就是第 k 大的元素
return;
else if(pivot > k - 1) // 如果基准元素的位置大于 k-1，那么第 k 大元素在其左半边，只需对左半边排序
quickSort(nums, left, pivot - 1, k);
else // 如果基准元素的位置小于 k-1，那么第 k 大元素在其右半边，只需对右半边排序
quickSort(nums, pivot + 1, right, k);
}
public:
int findKthLargest(vector<int>& nums, int k) {
quickSort(nums, 0, nums.size() - 1, k);
return nums[k - 1];
}
};
执行结果：
执行结果：通过
执行用时：8 ms, 在所有 C++ 提交中击败了 87.84% 的用户
内存消耗：9.8 MB, 在所有 C++ 提交中击败了 36.52% 的用户
解法三：堆排序（大根堆 O(NlogN)）
class Solution {
private:
// 交换数组中两个元素
void swap(vector<int>& nums, int idx1, int idx2)
{
int temp = nums[idx1];
nums[idx1] = nums[idx2];
nums[idx2] = temp;
}
// 调整堆
void adjustHeap(vector<int>& nums, int start, int end)
{
int dadIdx = start;
int sonIdx = dadIdx * 2 + 1;
while(sonIdx <= end)
{
if(sonIdx + 1 <= end && nums[sonIdx + 1] > nums[sonIdx])
sonIdx += 1;
if(nums[sonIdx] > nums[dadIdx])
{
swap(nums, sonIdx, dadIdx);
dadIdx = sonIdx;
sonIdx = dadIdx * 2 + 1;
}
else
return;
}
}
// 堆排序（大根堆）
void maxHeapSort(vector<int>& nums, int k)
{
int listLen = nums.size();
if(listLen <= 1)
return;
// 初始化建立堆
for(int i = listLen / 2 - 1; i >= 0; --i)
adjustHeap(nums, i, listLen - 1);
// 每次将堆首（最大值）移动到堆尾，重新调整剩下堆元素
// 因为取第 k 大，所以不需要进行完整排序，k 次即可
for(int i = 0; i < k; ++i)
{
swap(nums, 0, listLen - i - 1);
adjustHeap(nums, 0, listLen - i - 2);
}
}
public:
int findKthLargest(vector<int>& nums, int k) {
maxHeapSort(nums, k);
return nums[nums.size() - k];
}
};
执行结果：
执行结果：通过
执行用时：4 ms, 在所有 C++ 提交中击败了 98.74% 的用户
内存消耗：9.7 MB, 在所有 C++ 提交中击败了 72.34% 的用户
解法四：堆排序（小根堆 O(NlogK)）
class Solution {
private:
void adjustHeap(vector<int>& nums, int start, int end)
{
int dadIdx = start;
int sonIdx = dadIdx * 2 + 1;
while(sonIdx <= end)
{
if(sonIdx + 1 <= end && nums[sonIdx + 1] < nums[sonIdx])
sonIdx += 1;
if(nums[dadIdx] <= nums[sonIdx])
return;
else
{
swap(nums[sonIdx], nums[dadIdx]);
dadIdx = sonIdx;
sonIdx = dadIdx * 2 + 1;
}
}
}
void buildMinHeap(vector<int>& nums)
{
int size = nums.size();
for(int i = size / 2 - 1; i >= 0; --i)
adjustHeap(nums, i, size - 1);
}
public:
int findKthLargest(vector<int>& nums, int k) {
vector<int> minHeap;
// 先将 nums 的前 k 个数建立为小根堆
for(int i = 0; i < k; ++i)
minHeap.push_back(nums[i]);
buildMinHeap(minHeap);
// 遍历 nums 剩余元素，如果当前元素大于小根堆堆顶，则替换堆顶，重新调整堆
for(int i = k; i < nums.size(); ++i)
{
if(nums[i] > minHeap[0])
{
minHeap[0] = nums[i];
adjustHeap(minHeap, 0, k - 1);
}
}
// 最后小根堆的堆顶就是第 K 大的元素
return minHeap[0];
}
};
执行结果：
执行结果：通过
执行用时：12 ms, 在所有 C++ 提交中击败了 55.64% 的用户
内存消耗：9.8 MB, 在所有 C++ 提交中击败了 28.22% 的用户
扩展：求 const top k
如果传入的数组是 const vector<int> nums，也就是不能修改原数组的元素值，那么如何在 O(1) 的空间复杂度内实现查找第 k 大的元素？
解法：二分
- 时间复杂度
O(NlogN)：二分查找的时间复杂度是O(logN)，而对于每次二分的mid，调用count查找数组nums中大于等于mid的元素个数，时间复杂度为O(N) - 空间复杂度 O(1)
```cpp
class Solution {
private:
// 返回在 nums 数组中大于等于 x 的元素个数
int countLargerThanX(vector
nums, int x) {
}int size = nums.size(); int cnt = 0; for(int i = 0; i < size; ++i) { if(nums[i] >= x) ++cnt; } return cnt;
public:
int findKthLargest(vector
```
执行结果：通过
执行用时：4 ms, 在所有 C++ 提交中击败了 98.36% 的用户
内存消耗：11.7 MB, 在所有 C++ 提交中击败了 5.07% 的用户
若有收获，就点个赞吧
0 人点赞
