// 冒泡排序
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 判断边界条件
if(nums.size() == 0)
return 0;
// 冒泡排序
for(int i = 0; i < k; ++i)
{
for(int j = 1; j < nums.size(); ++j)
{
if(nums[j - 1] > nums[j])
swap(nums[j - 1], nums[j]);
}
}
// 返回第 k 大的数字
return *(nums.rbegin() + k - 1);
}
};
// 堆排序
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 判断边界条件
if(nums.size() == 0)
return 0;
// 初始化(默认大顶堆)
priority_queue<int> heap(nums.begin(), nums.end());
// 寻找第 k 大的元素
k--;
while(k--)
{
heap.pop();
}
return heap.top();
}
};
// 快速选择:“模板题”
// 随机选择一个数,大的放左边,小的放右边。
class Solution {
public:
int quick_select(vector<int>& nums, int l, int r, int k)
{
// 区间只有一个数的时候,直接返回
if(l == r)
return nums[l];
// 随机选择一个数
int num = nums[(l + r) >> 1];
int left = l - 1, right = r + 1;
while(left < right)
{
// 大的放左边,小的放右边
do left++; while(nums[left] > num);
do right--; while(nums[right] < num);
if(left < right)
swap(nums[left], nums[right]);
}
// 左边数组的个数大于 k
if(right >= k)
return quick_select(nums, l, right, k);
else
return quick_select(nums, right + 1, r, k);
}
int findKthLargest(vector<int>& nums, int k) {
// 判断边界条件
if(nums.size() == 0)
return 0;
// 快速选择(从 0 开始计数)
return quick_select(nums, 0, nums.size() - 1, k - 1);
}
};