C++で実現するO(1)の挿入・削除・ランダム取得データ構造（重複許可版）

本記事では、以下の3つの操作をすべてO(1)の計算量で実行できるデータ構造をC++で実装する方法を解説します。このデータ構造では、同じ値が複数回挿入されること（重複）が許可されている点がポイントです。

• insert(x): コレクションに値 x を挿入する
• remove(x): コレクションから値 x を削除する
• getRandom(): コレクションからランダムに1つの要素を取得する

アルゴリズムの考え方

これらの操作を高速に行うためには、「動的配列」と「ハッシュマップ」を組み合わせるのが有効です。具体的には、次の手順に従って実装します。

• ペア（値, インデックス）を格納する配列 nums を用意する
• 「値 → その値が nums 内に存在する位置のリスト」を管理するマップ m を用意する
• insert(val): val がまだ m に存在しない場合は true を返す。m[val] の末尾に nums の現在のサイズを追加し、nums の末尾に {val, m[val] のサイズ − 1} を追加して結果を返す
• remove(val): val が m に存在する場合のみ削除処理を行う。nums の末尾要素 last を取り出し、削除対象の要素の位置と入れ替えることで、配列の途中削除による O(n) のコストを回避する。その後 m[val] から該当インデックスを削除し、リストが空になった場合は m から val 自体も削除する
• getRandom(): nums からランダムに1つの要素を選んで返す

この「末尾要素との入れ替え」というテクニックにより、削除処理でも配列の再構築が不要になり、全体を O(1) で保つことができます。

C++実装例

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

#include <bits/stdc++.h>
using namespace std;
class RandomizedCollection {
public:
    vector <pair <int, int>> nums;
    unordered_map <int, vector<int>> m;
    RandomizedCollection() {
    }
    bool insert(int val) {
        bool ret = m.find(val) == m.end();
        m[val].push_back(nums.size());
        nums.push_back({val, m[val].size() - 1});
        return ret;
    }
    bool remove(int val) {
        bool ret = m.find(val) != m.end();
        if(ret){
            pair <int, int> last = nums.back();
            m[last.first][last.second] = m[val].back();
            nums[m[val].back()] = last;
            m[val].pop_back();
            if(m[val].empty())m.erase(val);
            nums.pop_back();
        }
        return ret;
    }
    int getRandom() {
        return nums[rand() % nums.size()].first;
    }
};
main(){
    RandomizedCollection ob;
    ob.insert(10);
    ob.insert(35);
    ob.insert(20);
    ob.insert(40);
    cout << (ob.getRandom()) << endl;
    ob.remove(20);
    cout << (ob.getRandom()) << endl;
}

入力例

10, 35, 20, 40 を順に挿入し、ランダムに1つ取得（例： 40）。その後 20 を削除し、再度ランダムに1つ取得（例： 35）。

出力例

40
35

まとめ

動的配列とハッシュマップを併用し、削除時に末尾要素と入れ替えることで、挿入・削除・ランダム取得のすべてを平均 O(1) の時間計算量で実現できます。重複を含むコレクションでも正しく動作する、実用的な設計パターンです。