两个有序数组间相加和的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]
  • 所以每次将这两种值扔进大根堆中,取出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问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程