挿入削除GetRandomO（1）-C++で許可される複製

一部の操作をサポートするデータ構造を作成したいとします。これらの操作は、O（1）時間で実行する必要があります。したがって、これらの操作を-

• insert（x）：コレクションにxを挿入します
• remove（x）：コレクションからxを削除します
• getRandom（）：これにより、そのコレクションからランダムな要素が検索されます。

これを解決するには、次の手順に従います-

• 配列番号を作成します
• 1つのマップを作成するm
• 関数insert（）を定義します。これにはvalが必要です。
• ret：=valがmにない場合
• m[val]の最後にnumsのサイズを挿入します
• numsの最後に{val、m [val] –1}ペアのサイズを挿入します
• return ret
• 関数remove（）を定義します。これにはvalが必要です。
• ret：=valがmにない場合
• retがゼロ以外の場合、-
  • last=numsの最後の要素
  • m[最後のキー][最後の値]：=m[val]の最後の要素
  • nums [[m [val]]の最後の要素：=最後
  • m[val]から最後の要素を削除します
  • m [val]が空の場合、-
    • mからvalを削除
  • numsから最後の要素を削除する
• return ret
• 関数getRandom（）を定義します
• コレクションからランダムな要素を1つ返します

理解を深めるために、次の実装を見てみましょう-

例

#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;
}

入力

Insert 10, 35, 20, 40, then get one random number, say 40, then remove 20, again get random element, that is say 35.

出力

40
35