C++で3つのソート済み配列の交差（共通要素）を求める方法

問題概要

厳密に増加順（昇順）にソートされた3つの整数配列 arr1、arr2、arr3 が与えられます。この中から、3つの配列すべてに出現する整数のみを含む、ソート済みの配列を返す必要があります。

例えば、配列が [1,2,3,4,5]、[1,2,5,7,9]、[1,3,4,5,8] である場合、3つすべてに共通して現れる整数は 1 と 5 のみなので、出力は [1,5] となります。

解決アプローチ

この問題は、ハッシュマップを使って各要素の出現回数を数えることで解決できます。手順は以下の通りです。

• 結果を格納するための配列 res を用意します
• 3つのマップ f1、f2、f3 を作成します
• i を 0 から arr1 の長さまで動かしながら、f1[arr1[i]] の値を1ずつ増やします
• 同じように、arr2 と arr3 についても各要素の出現回数を f2、f3 に記録します
• i を 1 から 2000 まで動かし、f1[i]・f2[i]・f3[i] のいずれも真（0以外）である場合、i を res に追加します
• 最後に res を返します

実装例

以下の実装例を見ると、より深く理解できるでしょう。

#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> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
      vector <int> ans;
      unordered_map <int,int> f1,f2,f3;
      for(int i =0;i<arr1.size();i++){
         f1[arr1[i]]++;
      }
      for(int i =0;i<arr2.size();i++){
         f2[arr2[i]]++;
      }
      for(int i =0;i<arr3.size();i++){
         f3[arr3[i]]++;
      }
      for(int i =1;i<=2000;i++){
         if(f1[i] && f2[i] && f3[i])ans.push_back(i);
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v1 = {1,2,3,4,5};
   vector<int> v2 = {1,2,5,7,9};
   vector<int> v3 = {1,3,4,5,8};
   print_vector(ob.arraysIntersection(v1, v2, v3));
}

入力

[1,2,3,4,5]
[1,2,5,7,9]
[1,3,4,5,8]

出力

[1,5]

計算量の分析

時間計算量は O(n + m + k + V) です。ここで n・m・k はそれぞれ3つの配列の長さ、V は最後に走査する値の範囲（この例では2000）を表します。また、空間計算量は O(n + m + k) となり、各配列の要素を出現回数マップに格納する分のメモリが必要です。

補足：さらに効率的な方法

3つの配列がすでにソートされているという性質を活かせば、ハッシュマップを使わない「3ポインタ法」でも解くことができます。これは、各配列に1つずつポインタを用意し、先頭側で最も小さい値を指すポインタを順に進めていき、3つのポインタが指す値が一致した時点でそれを共通要素として記録する方法です。この手法では時間計算量 O(n + m + k)、空間計算量 O(1) を実現でき、メモリ使用量を抑えられる点が大きな利点です。