Leetcode: 215. Kth Largest Elements in an Array数组中的第k个最大元素
发布日期:2021-09-14 15:32:58
浏览次数:8
分类:技术文章
本文共 1176 字,大约阅读时间需要 3 分钟。
Kth Largest Elements in an Array数组中的第k个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
输入:
[3,2,1,5,6,4] 和 k = 2
输出:
5
输入:
[3,2,3,1,2,4,5,5,6] 和 k = 4
输出:
4
你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。
方法1:堆
大顶堆
int findKthLargest(vector & nums, int k) { priority_queue q(nums.begin(), nums.end()); for (int i = 0; i < k - 1; ++i) { q.pop(); } return q.top(); }
方法2:快速排序
int findKthLargest(vector & nums, int k) { int left = 0, right = nums.size() - 1; while (true) { int pos = partition(nums, left, right); if (pos == k - 1) return nums[pos]; else if (pos > k - 1) right = pos - 1; else left = pos + 1; } } int partition(vector & nums, int left, int right) { int pivot = nums[left], l = left + 1, r = right; while (l <= r) { if (nums[l] < pivot && nums[r] > pivot) { swap(nums[l++], nums[r--]); } if (nums[l] >= pivot) ++l; if (nums[r] <= pivot) --r; } swap(nums[left], nums[r]); return r; }
转载地址:https://blog.csdn.net/weixin_42490152/article/details/100941103 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月08日 00时41分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
5.4 使用PostgreSQL数据库
2021-06-30
5.5 使用beedb库进行ORM开发
2021-06-30
5.6 NOSQL数据库操作
2021-06-30
第六章 session和数据存储
2021-06-30
6.1 session和cookie
2021-06-30
6.2 Go如何使用session
2021-06-30
7.5 文件操作
2021-06-30
12.4 备份和恢复
2021-06-30
第十三章 如何设计一个Web框架
2021-06-30
13.1 项目规划
2021-06-30
13.2 自定义路由器设计
2021-06-30
13.3 controller设计
2021-06-30
13.4 日志和配置设计
2021-06-30
13.5 实现博客的增删改
2021-06-30
第十四章 扩展Web框架
2021-06-30
Go语言教程拓展基础篇 (查漏补缺, 献给初学者)
2021-06-30
14.1 静态文件支持
2021-06-30
OS X v10.8 to OS X v10.9 API 差异
2021-06-30
cocos2dx多线程以及线程同步 与 cocos2dx内存管理与多线程问题
2021-06-30
cocos2dx python项目创建
2021-06-30