两个有序数组间相加和的Topk问题
2021/10/4 23:11:48
本文主要是介绍两个有序数组间相加和的Topk问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
- 两个有序数组间相加和的Topk问题
- 考查点:堆 + 哈希表
分析
- 数据是十万,所以考虑
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)以下的解法。因为是TopK问题,所以暗示用堆,每次从堆中取出最大值,所以需要大根堆。放入堆中的元素不能有重复,因此要使用哈希表判重。另外,最大值只能是两种情况。
- a数组往前移动一格,
a[i-1] + b[j]
- b数组往前移动一格,
a[i] + b[j-1]
- a数组往前移动一格,
- 所以每次将这两种值扔进大根堆中,取出k个值即为答案。
代码
#include <bits/stdc++.h> using namespace std; const int N = 1e5+10; int a[N], b[N]; using LL = long long; using VT = vector<LL>; int main(){ int n, k; cin>>n>>k; for(int i = 0; i < n; i++) cin>>a[i]; for(int i = 0; i < n; i++) cin>>b[i]; sort(a, a+n); sort(b, b+n); priority_queue<VT> pq; pq.push({a[n-1]+b[n-1],n-1,n-1}); unordered_set<pair<int, int>> st; while(k--){ auto t =pq.top(); pq.pop(); int sum = t[0], i=t[1],j=t[2]; printf("%d ",sum); if(i && !st.count({i-1,j})){ st.insert({i-1, j}); pq.push({a[i-1]+b[j],i-1,j}); } if(j && !st.count({i,j-1})){ st.insert({i, j-1}); pq.push({a[i]+b[j-1],i,j-1}); } } return 0; }
这篇关于两个有序数组间相加和的Topk问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南