C++で配列内のユニークな要素数をカウントする方法

本記事では、重複する要素を含むソートされていない配列が与えられたとき、その配列に含まれるユニークな（重複しない）要素の個数を求める方法を解説します。

配列とは、同じ型の要素を固定サイズで連続的に格納できるデータ構造の一種です。複数のデータをまとめて管理できるだけでなく、同じ型の変数の集合として捉えると、その利便性がより理解しやすくなります。

具体例

入力： int arr[] = {1, 1, 2, 3, 3, 4, 4}
出力： count is 4

説明： この配列には「1、2、3、4」の4種類のユニークな要素が含まれています。配列のサイズは7ですが、これは重複した要素が含まれているためです。つまり、重複を取り除いた上で残りの要素数を数えるのがこのタスクの目的です。

入力： int arr[] = {1, 2, 3, 4, 5, 5, 5, 5}
出力： count is 5

説明： この配列には「1、2、3、4、5」の5種類のユニークな要素が含まれています。配列のサイズは8ですが、重複分を除いて数えると答えは5となります。

プログラムで使用するアプローチ

方法1：sort関数を使う（ソートあり）

• 配列 arr[] を作成します。
• length() 関数を使って配列の長さを取得します。配列の要素数に応じた整数値が返されます。
• sort関数を呼び出し、引数として配列とそのサイズを渡して配列をソートします。
• ユニークな要素の個数を保存するための一時変数を用意します。
• i を0から始め、i が配列のサイズ未満である間ループを回します。
• ループ内では、「i < size-1 かつ arr[i] == arr[i+1]」の条件で while ループを実行します。
• while ループの中では i の値をインクリメントし、重複している間はインデックスを進めます。
• for ループの中で count の値をインクリメントします。
• count を返し、結果を出力します。

方法2：ソートせずにカウントする

• 配列 arr[] を作成します。
• length() 関数を使って配列の長さを取得します。
• ユニークな要素の個数を保存するための一時変数を用意します。
• i を1から始め、i が配列のサイズ未満である間ループを回します。
• ループ内で j を0に設定し、「j が i 未満である間 j を1ずつ増やしながら」内部ループを実行します。
• 内部ループでは、arr[i] == arr[j] の場合は break でループを抜けます。
• 内部ループ終了後、i == j であれば count を1増やします（それまでに同じ値が見つからなかった＝新しい要素ということ）。
• count を返し、結果を出力します。

サンプルコード

ソートを使用する場合

#include <algorithm>
#include <iostream>
using namespace std;
int distinct_elements(int arr[], int n){
    // 配列をソート
    sort(arr, arr + n);
    // ソート済み配列を走査
    int count = 0;
    for (int i = 0; i < n; i++){
        // 重複が見つかったらインデックスを進める
        while (i < n - 1 && arr[i] == arr[i + 1]){
            i++;
        }
        count++;
    }
    return count;
}
// メイン関数
int main(){
    int arr[] = { 3, 6, 5, 8, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "count is " << distinct_elements(arr, n);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

count is 6

入力配列 {3, 6, 5, 8, 2, 3, 4} の中には「3」が2回登場していますが、ユニークな要素は 2、3、4、5、6、8 の6種類です。ソート後は隣接する重複要素をスキップしながら走査することで、効率的に個数を数えられます。

サンプルコード

ソートを使用しない場合

#include <iostream>
using namespace std;
int countDistinct(int a[], int size){
    int i, j, count = 1;
    for (i = 1; i < size; i++){
        for (j = 0; j < i; j++){
            if (a[i] == a[j]){
                break;
            }
        }
        if (i == j){
            count++;
        }
    }
    return count;
}
// メイン関数
int main(){
    int a[] = { 3, 6, 5, 8, 2, 3, 4 };
    int size = sizeof(a) / sizeof(a[0]);
    cout << "count is " << countDistinct(a, size);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

count is 6

両手法の比較

ソートを使う方法は、計算量が O(n log n) となるため、大きな配列に対して効率的です。一方、元の配列の順序が変わってしまう点には注意が必要です。

ソートを使わない方法は二重ループによる O(n²) の計算量となり、配列が大きくなると処理時間が増加します。ただし、元の配列の順序を保持したい場合や、小規模なデータを扱う場合にはシンプルで有効なアプローチです。