C++で2つの配列の共通部分（積集合）を求める方法

プログラミングでは、2つの配列が与えられたときに、両方に共通して含まれる要素（共通部分・積集合）を求めたい場面がよくあります。

例えば、入力が [1,5,3,6,9] と [2,8,9,6,7] の場合、両方の配列に存在する要素は 9 と 6 なので、出力は [9, 6] になります。

解決のアプローチ

この問題は、ハッシュマップ（unordered_map）を使って各配列の要素の出現回数を記録することで、効率的に解くことができます。手順は以下の通りです。

• 2つのマップ mp1、mp2 を定義します
• 結果を格納するための配列 res を定義します
• nums1 の各要素 x について、mp1[x] を1増やします
• nums2 の各要素 x について、mp2[x] を1増やします
• mp1 の各キーと値のペア x に対して以下を処理します
  • カウンタ cnt を0で初期化します
  • cnt に「x の値」と「mp2[x のキー]」のうち小さい方を代入します
  • cnt > 0 である場合、つまり両方の配列にそのキーが存在する場合は、キーを res の末尾に追加します
• res を返します

この手法では、マップへの登録と参照が平均 O(1) で行えるため、配列の長さを n と m とすると、全体の計算量は O(n + m) となり、非常に効率的です。

実装例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2){
        unordered_map<int, int> mp1, mp2;
        vector<int> res;
        for (auto x : nums1)
            mp1[x]++;
        for (auto x : nums2)
            mp2[x]++;
        for (auto x : mp1) {
            int cnt = 0;
            cnt = min(x.second, mp2[x.first]);
            if (cnt > 0)
                res.push_back(x.first);
        }
        return res;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,5,3,6,9}, v1 = {2,8,9,6,7};
    print_vector(ob.intersection(v, v1));
}

入力

{1,5,3,6,9},{2,8,9,6,7}

出力

[9, 6]

コードのポイント

unordered_map は要素の順序を保証しないため、出力結果の並び順（ここでは [9, 6]）は実行環境によって変わる可能性があります。順序を整えたい場合は、結果をソートするか、map を使用するとよいでしょう。また、このアルゴリズムは重複する要素があっても正しく動作し、両方の配列に存在する要素だけを確実に抽出できます。