C++で配列内の出現回数が異なる唯一の要素を見つける方法

問題概要

N個の数値からなる配列があり、そのうち1つの要素を除いて、すべての要素が同じ回数(m回、この値も与えられる)だけ出現するとします。この「例外となる要素」を見つけるのが課題です。

例えば、入力が A = [6, 2, 7, 2, 2, 6, 6]、m = 3 の場合を考えてみましょう。ほとんどの要素は3回ずつ現れていますが、7だけは1回しか現れないため、出力は 7 となります。

解法のアプローチ:ビットごとのカウント

この問題は、各ビット位置に注目するビット演算のテクニックを使うことで効率的に解くことができます。手順は以下の通りです。

• INT_SIZE := 整数型変数のバイトサイズ × 8(= ビット数)
• INT_SIZE のサイズを持つ配列 count を定義し、すべて 0 で初期化します。
• i = 0 から INT_SIZE - 1 まで繰り返します。
  • j = 0 から size - 1 まで繰り返します。
  • (arr[j] AND 2ⁱ) が 0 でない場合、count[i] を 1 増やします。
• res := 0 として初期化します。
• i = 0 から INT_SIZE - 1 まで繰り返し、res := res + ((count[i] mod m) × 2ⁱ) を計算します。
• res を返します。

なぜこの方法が機能するのか

各要素がちょうどm回出現しているなら、任意のビット位置における「1になっているビット」の総数も必ずmの倍数になります。ところが、1回だけ現れる特別な要素が存在すると、その要素のビットが立っている位置ではカウントがmの倍数からずれます。したがって、count[i] % m を計算すれば、それがそのまま一意な要素の第iビットになります。全ビット位置についてこの値を組み合わせれば、目的の要素を正確に復元できるという仕組みです。

C++実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int selectUnique(unsigned int arr[], int size, int m){
    int INT_SIZE = 8 * sizeof(unsigned int);
    int count[INT_SIZE];
    memset(count, 0, sizeof(count));
    for(int i = 0; i < INT_SIZE; i++)
        for(int j = 0; j < size; j++)
            if((arr[j] & (1 << i)) != 0)
                count[i] += 1;
    unsigned res = 0;
    for(int i = 0; i < INT_SIZE; i++)
        res += (count[i] % m) * (1 << i);
    return res;
}
main(){
    unsigned int arr[] = { 6, 2, 5, 2, 2, 6, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int m = 3;
    cout << selectUnique(arr, size, m);
}

実行結果

入力:

{ 6, 2, 5, 2, 2, 6, 6 }

出力:

5

計算量について

このアルゴリズムの時間計算量は O(INT_SIZE × N) ですが、INT_SIZE は固定値(32ビット環境では32)であるため、実質的には O(N) の線形時間で動作します。また、必要な補助メモリは count 配列のみで O(INT_SIZE)、つまり定数空間に抑えられる点も大きな利点です。ハッシュマップなどを使う方法と比べて、追加のデータ構造が不要でメモリ効率に優れています。