当前位置:网站首页>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);
}
};
边栏推荐
- STM8S105K4T6------串口发送和接收
- keytool命令
- C语言--环形缓存区
- 2022G1工业锅炉司炉考试练习题及模拟考试
- 在更一般意义上验算移位距离和假设
- 如何在MySQL中的数据库下删除所有的表
- 第08章 索引的创建与设计原则【2.索引及调优篇】【MySQL高级】
- There are too many systems, how to realize multi-account interworking?
- STM8S105K4T6------Serial port sending and receiving
- mpf5_定价Bond_yield curve_Spot coupon_duration_有效利率_连续复利_远期_Vasicek短期_CIR模型Derivatives_Tridiagonal_ppf
猜你喜欢
数据安全峰会2022 | 美创DSM获颁“数据安全产品能力验证计划”评测证书
织梦内核电动伸缩门卷闸门门业公司网站模板 带手机版【站长亲测】
Countdown to 2 days, the "New Infrastructure of Cultural Digital Strategy and Ecological Construction of Cultural Art Chain" will kick off soon
STM8S105k4t6c--------------点亮LED
在更一般意义上验算移位距离和假设
2022焊工(初级)上岗证题目模拟考试平台操作
How to drop all tables under database in MySQL
全网没有之一的JMeter 接口测试流程详解
瑞能微计量芯片RN2026的实用程序
Architecture of the actual combat camp module three operations
随机推荐
单片机C语言->的用法,和意思
香港服务器有哪些常用的型号
在更一般意义上验算移位距离和假设
数据安全峰会2022 | 美创DSM获颁“数据安全产品能力验证计划”评测证书
How many ways do you know about communication between multiple threads?
DHCP服务详解
Ant - the design of the Select component using a custom icon (suffixIcon attribute) suffixes, click on the custom ICONS have no reaction, will not display the drop-down menu
STM8S-----选项字节
View mysql deadlock syntax
查看mysql死锁语法
Deep Learning (3) Classification Theory Part
织梦内核电动伸缩门卷闸门门业公司网站模板 带手机版【站长亲测】
安装postgis时报找不到“POSTGIS_VERSION”这个函数
Example 041: Methods and variables of a class
Example 039: Inserting elements into an ordered list
In the season of going overseas, the localization of Internet tips for going overseas
MySQL高级-读写分离-分库分表
STM32-遥感数据处理
How to read the resources files in the directory path?
2022年T电梯修理考题及答案