公式
B - 積集合/intersection 解説 by sugarrr
まず、\(2\) 重ループを用いて数列 \(A\) と数列 \(B\) の両方に含まれる要素を全て列挙しましょう。
次に、それらの要素を昇順にソートして、出力すれば良いです。
\(2\) 重ループを回すところがボトルネックになり、計算量は \(O(NM)\) です。
以下に実装例を示すので参考にしてください。
C++での実装例:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
signed main(){
ll n,m;cin>>n>>m;
vector<ll> a(n),b(m);
rep(i,0,n-1)cin>>a[i];
rep(i,0,m-1)cin>>b[i];
vector<ll>ans;
rep(i,0,n-1){
rep(j,0,m-1){
if(a[i]==b[j]){
ans.push_back(a[i]);
}
}
}
sort(ans.begin(),ans.end());
for(auto x:ans)cout<<x<<" ";
cout<<endl;
return 0;
}
投稿日時:
最終更新: