当前位置:网站首页>剑指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/
边栏推荐
- 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
- [Unity Entry Plan] Handling of Occlusion Problems in 2D Games & Pseudo Perspective
- DAY22:sqli-labs 靶场通关wp(Less01~~Less20)
- Using OpenVINO to implement the flying paddle version of the PGNet inference program
- How to simply implement the quantization and compression of the model based on the OpenVINO POT tool
- 蚁剑高级模块开发
- Greenplum Database Fault Analysis - Why Does gpstart -a Return Failure After Version Upgrade?
- [ROS](10)ROS通信 —— 服务(Service)通信
- 行业案例|世界 500 强险企如何建设指标驱动的经营分析系统
- 如何基于OpenVINO POT工具简单实现对模型的量化压缩
猜你喜欢
[Decryption] Can the NFTs created by OpenSea for free appear in my wallet without being chained?
迁移学习——Joint Geometrical and Statistical Alignment for Visual Domain Adaptation
Intel XDC 2022 Wonderful Review: Build an Open Ecosystem and Unleash the Potential of "Infrastructure"
Quickly learn chess from zero to one
Pisanix v0.2.0 发布|新增动态读写分离支持
Tree search (bintree)
Leetcode brushing questions - 22. Bracket generation
sql语句多字段多个值如何进行排序
【解密】OpenSea免费创造的NFT都没上链竟能出现在我的钱包里?
iNFTnews | What can NFTs bring to the sports industry and fans?
随机推荐
多线程(2)
select tag custom style
亚马逊云科技 + 英特尔 + 中科创达为行业客户构建 AIoT 平台
高数_复习_第1章:函数、极限、连续
HOG特征学习笔记
LeetCode使用最小花费爬楼梯----dp问题
.Net C# Console Create a window using Win32 API
DAY22:sqli-labs 靶场通关wp(Less01~~Less20)
SuperMap支持的国产环境汇总
意识形态的机制
How to deal with your own shame
Flink 1.15.1 集群搭建(StandaloneSession)
How to simply implement the quantization and compression of the model based on the OpenVINO POT tool
[Decryption] Can the NFTs created by OpenSea for free appear in my wallet without being chained?
Domain Driven Design - MDD
DAY22: sqli-labs shooting range clearance wp (Less01~~Less20)
The 2022 EdgeX China Challenge will be grandly opened on August 3
dotnet 6 为什么网络请求不跟随系统网络代理变化而动态切换代理
source program in assembly language
HOG feature study notes