公式

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;
}

投稿日時:
最終更新: