【C++】整数配列から重複を除いた一意の要素を出力する3つの方法

問題概要

この記事では、整数値の配列が与えられたときに、その配列に含まれる重複しない(一意の)要素だけを出力する方法を解説します。出力には、同じ値が何度現れても1度だけ含まれるようにします。

入出力例

Input: array = {1, 5, 7, 12, 1, 6, 10, 7, 5}
Output: 1 5 7 12 6 10

上記の例では、1・5・7 がそれぞれ2回ずつ現れていますが、出力ではそれぞれ1度だけ表示されています。

方法1: 二重ループで重複をチェックする

最もシンプルなアプローチは、各要素についてそれ以前の要素と比較し、初めて登場した要素のみを出力する方法です。外側のループで各要素を取り出し、内側のループでそれより前方の要素と照合します。一致する要素が存在しなければ、その値は初登場なので出力します。

#include <iostream>
using namespace std;

void printDistinctValues(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < i; j++)
            if (arr[i] == arr[j])
                break;
        if (i == j)
            cout << arr[i] << "\t";
    }
}

int main() {
    int arr[] = {1, 5, 7, 12, 1, 6, 10, 7, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Distinct values of the array are :\n";
    printDistinctValues(arr, n);
    return 0;
}

実行結果

Distinct elements of the array are −
1 5 7 12 6 10

この方法は実装が非常に簡単ですが、二重ループを使用するため時間計算量は O(n²) となります。要素数が多い配列では処理が遅くなる点が弱点です。

方法2: ソートを利用する

配列をあらかじめソートしておくと、同じ値どうしが連続して並ぶようになります。これにより、隣接する要素同士を比較するだけで重複を検出できるため、効率的に一意の要素を取り出せます。

#include <bits/stdc++.h>
using namespace std;

void printDistinctElements(int arr[], int n) {
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        while (i < n - 1 && arr[i] == arr[i + 1])
            i++;
        cout << arr[i] << "\t";
    }
}

int main() {
    int arr[] = {1, 5, 7, 12, 1, 6, 10, 7, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Distinct elements of the array are :\n";
    printDistinctElements(arr, n);
    return 0;
}

実行結果

Distinct elements of the array are −
1 5 6 7 10 12

この方法の時間計算量は O(n log n)(ソートのコストが支配的)です。ただし、元の配列の順序が失われ、また配列自体が書き換えられる点には注意が必要です。

方法3: unordered_setで訪問済み要素を管理する(推奨)

最も効率的なのが、ハッシュセットである std::unordered_set を使って「すでに出力した要素」を記録する方法です。配列を先頭から走査し、セットに未登録の要素だけを出力すると同時にセットへ挿入していきます。これにより、元の順序を保ちながら O(n) の時間計算量で処理できます。

#include <bits/stdc++.h>
using namespace std;

void printDistinctElements(int arr[], int n) {
    unordered_set<int> visited;
    for (int i = 0; i < n; i++) {
        if (visited.find(arr[i]) == visited.end()) {
            visited.insert(arr[i]);
            cout << arr[i] << "\t";
        }
    }
}

int main() {
    int arr[] = {1, 5, 7, 12, 1, 6, 10, 7, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Distinct numbers of the array are :\n";
    printDistinctElements(arr, n);
    return 0;
}

実行結果

Distinct numbers of the array are −
1 5 7 12 6 10

3つの方法の比較まとめ

パフォーマンスと順序の保持を両立したい場合は、方法3の unordered_set を使う手法がベストチョイスです。一方、小規模なデータや学習目的であれば、シンプルな二重ループでも十分実用的です。用途に応じて適切な方法を選びましょう。