要素の範囲が制限されていない配列の重複をC++で検出する方法

N個の整数からなる配列が与えられたとします。ここでは、その配列に含まれる重複要素を出力する方法を解説します。重複が1つも存在しない場合は、-1を返します。

例えば、配列が [12, 15, 12, 3, 6, 12, 3, 48, 56, 8, 48] の場合、重複している要素は [12, 3, 48] となります。

この問題は、C++の unordered_map（ハッシュマップ）を使うことで効率的に解決できます。要素の値の範囲が制限されていない場合でも、ハッシュマップを利用すれば各要素の出現回数を簡単に記録できます。

アルゴリズムの考え方

基本的な手順は以下のとおりです。

1. 各要素の出現回数を記録するための unordered_map を用意します。
2. 配列を1回走査し、各要素の出現回数をカウントします。要素がマップに存在しない場合は新たに追加し、すでに存在する場合はカウントを増やします。
3. マップを走査し、出現回数が2以上の要素を重複要素として出力します。
4. 重複要素が1つも見つからなかった場合は、-1 を出力します。

ハッシュマップを使用することで、挿入と検索を平均 O(1) で行えるため、全体の時間計算量は O(n)、空間計算量も O(n) となります。これは要素の値の範囲に依存しないため、大きな値や負の値が含まれる配列にも対応できます。

サンプルコード

#include<iostream>
#include<unordered_map>
using namespace std;
void displayDuplicates(int arr[], int n) {
   unordered_map<int, int> occurrence;
   for (int i=0; i<n; i++)
   occurrence[arr[i]]++;
   bool duplicate = false;
   unordered_map<int, int>:: iterator itr;
   for (itr=occurrence.begin(); itr!=occurrence.end(); itr++) {
      if (itr->second > 1) {
         cout << itr->first << " ";
         duplicate = true;
      }
   }
   if (duplicate == false)
   cout << "-1";
}
int main() {
   int arr[] = {12, 15, 12, 3, 6, 12, 3, 48, 56, 8, 48};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Duplicate elements are: ";
   displayDuplicates(arr, n);
}

実行結果

Duplicate elements are: 12 3 48

コードのポイント

• occurrence[arr[i]]++ の1行で、要素の登録とカウントの増加を同時に行っています。unordered_map は存在しないキーにアクセスした際に自動的に値を0で初期化するため、事前の初期化が不要です。
• duplicate フラグを用いて、重複が見つからなかった場合に -1 を出力する処理を実現しています。
• マップの走査順序はハッシュ値に依存するため、出力順序は配列内の出現順序とは一致しない点に注意してください。

このように、unordered_map を活用すれば、要素の値の範囲に制限がない配列でも、線形時間で重複要素を効率的に検出できます。