当前位置:网站首页>Power button (LeetCode) 215. The first K largest elements in the array (2022.08.03)
Power button (LeetCode) 215. The first K largest elements in the array (2022.08.03)
2022-08-04 03:03:00 【ChaoYue_miku】
给定整数数组 nums 和整数 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
提示:
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/kth-largest-element-in-an-array
方法一:快速排序
C++提交内容:
class Solution {
public:
int quickSelect(vector<int>& a, int l, int r, int index) {
int q = randomPartition(a, l, r);
if (q == index) {
return a[q];
} else {
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}
}
inline int randomPartition(vector<int>& a, int l, int r) {
int i = rand() % (r - l + 1) + l;
swap(a[i], a[r]);
return partition(a, l, r);
}
inline int partition(vector<int>& a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a[++i], a[j]);
}
}
swap(a[i + 1], a[r]);
return i + 1;
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}
};
边栏推荐
猜你喜欢
随机推荐
MySQL查询优化与调优
如果禁用了安全启动,GNOME 就会发出警告
C program compilation and predefined detailed explanation
There are n steps in total, and you can go up to 1 or 2 steps each time. How many ways are there?
WPE详细教程
Oracle迁移到瀚高之后,空值问题处理
跨境电商看不到另一面:商家刷单、平台封号、黑灰产牟利
香港服务器有哪些常用的型号
数据湖(二十):Flink兼容Iceberg目前不足和Iceberg与Hudi对比
Qt中对象树的机制介绍以及底层实现,各种结果分析:(以及自己写容易犯错的点)
Simple record of Flink principle flow chart
逻辑漏洞----其他类型
MallBook联合人民交通出版社,推动驾培领域新发展,开启驾培智慧交易新生态
【学习笔记之菜Dog学C】动态内存管理
织梦响应式酒店民宿住宿类网站织梦模板(自适应手机端)
Presto中broadcast join和partition join执行计划的处理过程
In the season of going overseas, the localization of Internet tips for going overseas
How to read the resources files in the directory path?
yum 仅下载包
第08章 索引的创建与设计原则【2.索引及调优篇】【MySQL高级】