当前位置:网站首页>剑指offer专项突击版第20天
剑指offer专项突击版第20天
2022-08-05 02:26:00 【hys__handsome】
小顶堆
- 第k大就等同于,序列升序后倒数第k个数。
- 容易发现,倒数第k个之前的数都用不到了,那么我们可以扔掉那些没用的,然后保持插入后序列仍然有序即可。
- 由于这里add会操作 1 0 4 10^4 104 次,所以需要较小的时间复杂度,容易想到使用堆结构(大小保持为<= k k k ),或者multiset。
class KthLargest {
public:
int k = 0;
priority_queue<int,vector<int>,greater<int>> heap;
KthLargest(int k, vector<int>& nums) {
for(int num: nums) heap.push(num);
this->k = k;
}
int add(int val) {
heap.push(val);
while(heap.size() > k) heap.pop();
return heap.top();
}
};
剑指 Offer II 060. 出现频率最高的 k 个数字
方法一、使用哈希表记录次数,然后遍历哈希表让堆来维护前 k k k 大,时间复杂度就为 O ( N l o g k ) O(Nlogk) O(Nlogk) 。
class Solution {
public:
typedef pair<int,int> PII;
unordered_map<int,int> cnts;
static bool cmp(const PII &a, const PII &b) {
return a.second > b.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
for(int num: nums) {
cnts[num]++;
}
//自定义排序规则
priority_queue<PII,vector<PII>,decltype(&cmp)> heap(cmp);
for(auto p: cnts) {
if(heap.size() == k) {
//保持堆大小不大于k
if(heap.top().second < p.second) {
heap.pop();
heap.emplace(p);
}
} else heap.emplace(p);
}
vector<int> res;
while(heap.size()) {
res.emplace_back(heap.top().first);
heap.pop();
}
return res;
}
};
方法二、使用哈希表记录次数,然后再排序取出前k大的数即可。时间 O ( N l o g N ) O(NlogN) O(NlogN)
class Solution {
public:
unordered_map<int,int> cnts;
static bool cmp(const pair<int,int> &a, const pair<int,int> &b) {
return a.second > b.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
int maxx = 0;
for(int num: nums) {
cnts[num]++;
}
vector<pair<int,int>> ls;
for(auto p: cnts) {
ls.emplace_back(p);
}
sort(ls.begin(),ls.end(),cmp);
ls.erase(ls.begin()+k,ls.end());
vector<int> res;
for(auto num: ls) res.emplace_back(num.first);
return res;
}
};
- 容易想到一个方法:暴力出所有数对,然后排序取前 k k k 小,时间复杂度是 O ( N 2 ) O(N^2) O(N2) 在这里会超时。
- 仔细思考会发现, n u m s 1 [ 0 ] + n u m s 2 [ 0 ] nums1[0]+nums2[0] nums1[0]+nums2[0] 一定是最小的,然后接下第二小肯定是它们其中之一: n u m s 1 [ 0 ] + n u m s 2 [ 1 ] nums1[0]+nums2[1] nums1[0]+nums2[1] 、 n u m s 1 [ 1 ] + n u m s 2 [ 0 ] nums1[1]+nums2[0] nums1[1]+nums2[0] ,以此类推,这样我们就不用遍历出所有数对了只需利用规律找出前几个即可,这里需要用小顶堆来维护数对间的关系。
class Solution {
public:
typedef pair<int,int> PII;
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto cmp = [&nums1,&nums2](const PII &a, const PII &b) {
return nums1[a.first]+nums2[a.second] > nums1[b.first]+nums2[b.second];
};
int n = nums1.size();
int m = nums2.size();
priority_queue<PII,vector<PII>,decltype(cmp)> heap(cmp);
for(int i = 0; i < min(k,n); i++) {
heap.emplace(i,0);
}
vector<vector<int>> res;
while(k-- && heap.size()) {
auto [x,y] = heap.top();
heap.pop();
res.push_back({
nums1[x],nums2[y]});
if(y+1 < m) heap.emplace(x,y+1);
}
return res;
}
};
参考:https://leetcode.cn/problems/qn8gGX/solution/he-zui-xiao-de-k-ge-shu-dui-by-leetcode-eoce6/
边栏推荐
- leetcode 15
- 意识形态的机制
- Leetcode刷题——22. 括号生成
- DAY23: Command Execution & Code Execution Vulnerability
- KingbaseES V8 GIS data migration solution (2. Introduction to the capabilities of Kingbase GIS)
- mysql树状结构查询问题
- nodeJs--encapsulate routing
- [Word] #() error occurs after Word formula is exported to PDF
- 亚马逊云科技携手中科创达为行业客户构建AIoT平台
- The 2022 EdgeX China Challenge will be grandly opened on August 3
猜你喜欢
Transfer Learning - Distant Domain Transfer Learning
C语言实现简单猜数字游戏
RAID磁盘阵列
海量服务实例动态化管理
select tag custom style
J9数字货币论:web3的创作者经济是什么?
【MySQL series】- Does LIKE query start with % will make the index invalid?
ExcelPatternTool: Excel table-database mutual import tool
The 2022 EdgeX China Challenge will be grandly opened on August 3
Log an error encountered when compiling google gn "I could not find a ".gn" file ..."
随机推荐
.Net C# Console Create a window using Win32 API
高数_复习_第1章:函数、极限、连续
J9数字货币论:web3的创作者经济是什么?
[ROS] (10) ROS Communication - Service Communication
如何逐步执行数据风险评估
线性表的查找
Understand the recommendation system in one article: Recall 06: Two-tower model - model structure, training method, the recall model is a late fusion feature, and the sorting model is an early fusion
力扣-相同的树
01 [Foreword Basic Use Core Concepts]
Leetcode刷题——22. 括号生成
C language basics -- pointers
nodeJs--encapsulate routing
<开发>实用工具
使用SuperMap iDesktopX数据迁移工具迁移ArcGIS数据
C学生管理系统 头添加学生节点
Utilities 【日常训练】1403. 非递增顺序的最小子序列
iNFTnews | What can NFTs bring to the sports industry and fans?
采用redis缓存的linux主从同步服务器图片硬盘满了移到新目录要修改哪些指向
树形查找(二叉查找树)