C++でビット配列を活用して配列内の重複要素を検出する方法

概要

n個の数値からなる配列が与えられます(nは最大32,000)。この配列には重複した要素が含まれている可能性がありますが、nの値は事前には分かりません。ここでの課題は、利用可能なメモリがわずか4キロバイトという厳しい制約のもとで、配列内のすべての重複要素をどのように検出・表示するかというものです。

入力例

arr[] = {2, 6, 2, 11, 13, 11}

出力例

2 11
2と11は、与えられた配列内で複数回出現しています。

入力例

arr[] = {60, 50, 60}

出力例

60

アプローチ

4キロバイトのメモリがあるということは、最大で 8 × 4 × 2¹⁰ ビット(約327,680ビット)まで扱えることを意味します。32 × 2¹⁰ ビットは32,000よりも大きいため、各ビットが1つの整数に対応する32,000ビットのビットベクタを作成することができます。

また、32,000ビットを超えるビットベクタが必要になった場合でも、同様の方法で簡単に拡張できる点にも注目してください。このビットベクタを用いることで、配列を順番に走査しながら、各要素 v に対して「ビット v を1にセット」してフラグを立てていきます。そして、走査中にすでにフラグが立っている要素(= 重複要素)に遭遇したら、その値を出力します。

仕組みのポイント

• 右シフト演算(pos >> 5):32で割ることと同じ意味であり、対象のビットが格納されている整数のインデックスを求めます。
• ビットマスク(pos & 0x1F):31(0x1F)との論理積を取ることで、その整数内におけるビット番号(0〜31)を特定します。
• 計算量:時間計算量は O(n)、必要な追加メモリは約4KB(32,000ビット ≒ 4,000バイト)に抑えられます。

C++による実装例

// 配列内のすべての重複を出力するC++プログラム
#include <bits/stdc++.h>
using namespace std;

// 整数の配列を用いてビット配列を表現するクラス
class BitArray{
   int *arr1;
   public:
   BitArray() {}
   // コンストラクタ
   BitArray(int n1){
      // 32で割る処理。nビットを格納するには
      // n/32 + 1 個の整数が必要(intが32ビットの場合)
      arr1 = new int[(n1 >> 5) + 1];
   }
   // 指定位置のビット値を取得
   bool get(int pos1){
      // 32で割り、対応する整数の位置を求める
      int index1 = (pos1 >> 5);
      // arr[index] 内のビット番号を求める
      int bitNo1 = (pos1 & 0x1F);
      // 指定されたビットの値を判定して返す
      return (arr1[index1] & (1 << bitNo1)) != 0;
   }
   // 指定位置のビットをセット
   void set(int pos1){
      // ビット位置のインデックスを求める
      int index1 = (pos1 >> 5);
      // arr1[index1] 内の該当ビットをセット
      int bitNo1 = (pos1 & 0x1F);
      arr1[index1] |= (1 << bitNo1);
   }
   // すべての重複を出力するメイン関数
   void checkDuplicates1(int arr1[], int n1){
      // 32000ビットのビット配列を作成
      BitArray ba1 = BitArray(320000);
      // 配列要素を順に走査
      for (int i = 0; i < n1; i++){
         // ビット配列上のインデックスに相当する値
         int num1 = arr1[i];
         // numがすでにビット配列に存在する場合(重複)
         if (ba1.get(num1))
            cout << num1 << " ";
         // 存在しない場合はビットをセットして登録
         else
            ba1.set(num1);
      }
   }
};
// ドライバーコード
int main(){
   int arr1[] = {2, 6, 2, 11, 13, 11};
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   BitArray obj1 = BitArray();
   obj1.checkDuplicates1(arr1, n1);
   return 0;
}

実行結果

2 11