【C++入門】配列内の重複（繰り返し）要素を検索する方法

このチュートリアルでは、与えられた配列の中から繰り返し（重複）要素を見つけ出すプログラムをC++で作成します。

まずは、問題を解決するための基本的な手順を確認しましょう。

アルゴリズムの手順

• 配列を初期化します。
• 配列内の各要素の出現回数を記録するためのカウンタ用マップ（map）を初期化します。
• 配列を先頭から順に走査します。
  • 各要素の出現回数をカウントしていきます。
• 出現回数が1より大きい（2回以上現れる）要素を出力します。

サンプルコード

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

#include <bits/stdc++.h>
using namespace std;
int findRepeatingElement(int arr[], int n) {
    map<int, int> frequencies;
    for (int i = 0; i < n; i++) {
        map<int, int>::iterator itr = frequencies.find(arr[i]);
        if (itr != frequencies.end()) {
            itr->second = itr->second + 1;
        }
        else {
            frequencies.insert({arr[i], 1});
        }
    }
    for (map<int, int>::iterator itr = frequencies.begin(); itr != frequencies.end(); ++itr) {
        if (itr->second > 1) {
            return itr->first;
        }
    }
}
int main() {
    int arr[] = {1, 2, 3, 3, 4, 5, 5, 6};
    cout << findRepeatingElement(arr, 8) << endl;
    return 0;
}

コードの解説

findRepeatingElement 関数では、まず空の map を用意し、配列の各要素について以下の処理を行います。

• 要素がマップに存在しない場合： その要素をキーとして出現回数 1 で登録します。
• 要素がすでに存在する場合： 対応するカウント値を +1 して更新します。

すべての要素のカウントが終わったら、マップを走査して出現回数が 1 を超えている最初の要素を返します。上記の例では、配列 {1, 2, 3, 3, 4, 5, 5, 6} の中で 3 と 5 が重複していますが、マップはキー順にソートされて格納されるため、より小さい 3 が返されます。

実行結果

上記のコードを実行すると、次のような結果が得られます。

3

計算量について

このアルゴリズムでは std::map（平衡二分探索木）を使用しているため、要素の挿入・検索にはそれぞれ O(log n) のコストがかかり、全体の時間計算量は O(n log n) となります。

より高速な O(n) の解法を求める場合は、ハッシュテーブルベースの std::unordered_map を使う方法が有効です。また、要素の値の範囲が限定されている場合には、出現フラグを管理する配列を利用することでさらにシンプルに実装できます。

まとめ

このチュートリアルでは、C++の map を活用して配列内の重複要素を検索する方法を学びました。頻度カウントの考え方は、重複検出以外にもさまざまなアルゴリズム問題で応用できる基本的なテクニックなので、ぜひマスターしておきましょう。

本チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。