解决面试问题中的top k问题 Leetcode
2023-09-14 09:11:37 时间
https://leetcode.com/problems/kth-largest-element-in-an-array/
使用堆,堆插入一个数据是logk,删除一个数据是logk,复杂度为logk
Java
class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minQueue = new PriorityQueue<>(k); for (int num : nums) { if (minQueue.size() < k || num > minQueue.peek()) minQueue.offer(num); if (minQueue.size() > k) minQueue.poll(); } return minQueue.peek(); } }
C++的
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int> >pq; for(auto num:nums) { if(pq.size()<k) pq.push(num); else if(num>pq.top()) pq.pop(),pq.push(num); } return pq.top(); } };
使用快速选择,就是用快排改的,将数组分组,但是这个也是一个不稳定的做法
相关文章
- ☆打卡算法☆LeetCode 217. 存在重复元素 算法解析
- 日拱一卒,LeetCode周赛287,训练你的逆向思维
- LeetCode–046–全排列(java)
- Array相关LeetCode题目笔记
- 【Leetcode 346/700】79. 单词搜索-回溯深度搜索JavaScript版
- 滑动窗口求最大值 leetcode 59
- LeetCode每日一题06-13
- LeetCode周赛285,再次翻车,时隔6年,没能写出的线段树
- leetcode 234. 回文链表 js 实现
- 前端工程师leetcode算法面试必备-简单的二叉树
- 刷完这19道leetcode二分查找算法,不信进不了大厂
- 前端工程师leetcode算法面试之二分搜索算法(上)
- LeetCode和面试中的常客,巧妙的两指针算法
- LeetCode 算法题
- 前端工程师leetcode算法面试必备---二分搜索算法(下)
- 【leetcode 206】 反转链表(简单)
- LeetCode每日一题:实现strStr()