Leetcode

LeetCode＃380-挿入削除GetRandom O（1）



Leetcode 380 Insert Delete Getrandom O



件名の説明：

次のすべての操作をサポートするデータ構造を設計します。 平均 または（1） 時間。



  1. insert(val)：まだ存在しない場合は、アイテムvalをセットに挿入します。
  2. remove(val)：存在する場合、セットからアイテムvalを削除します。
  3. getRandom：現在の要素のセットからランダムな要素を返します。各要素には、 同じ確率 返されるの。

例：

// Init an empty set. RandomizedSet randomSet = new RandomizedSet() // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomSet.insert(1) // Returns false as 2 does not exist in the set. randomSet.remove(2) // Inserts 2 to the set, returns true. Set now contains [1,2]. randomSet.insert(2) // getRandom should return either 1 or 2 randomly. randomSet.getRandom() // Removes 1 from the set, returns true. Set now contains [2]. randomSet.remove(1) // 2 was already in the set, so return false. randomSet.insert(2) // Since 2 is the only number in the set, getRandom always return 2. randomSet.getRandom()

挿入、削除、これらの操作のいずれかが1つの要素を取るように設計されたデータ構造は、O（1）時間計算量です。基になるデータ構造で使用されるベクトル、挿入はO（1）であり、要素には時間計算量もO（1）ですが、削除はO（n）であり、それぞれがハッシュ補助テーブルになります。ハッシュテーブルでは、挿入のラベルが付けられて次の処理を実行します。毎回、最後の要素を削除して要素の位置を入れ替え、最後の要素を削除します。



class RandomizedSet { public: /** Initialize your data structure here. */ RandomizedSet() {} /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ bool insert(int val) { if(hash.count(val)) return false else { nums.push_back(val) hash[val]=nums.size()-1 return true } } /** Removes a value from the set. Returns true if the set contained the specified element. */ bool remove(int val) { if(hash.count(val)) { int pos=hash[val] hash[nums.back()]=pos swap(nums[pos],nums.back()) nums.pop_back() hash.erase(val) return true } else return false } /** Get a random element from the set. */ int getRandom() { return nums[rand()%nums.size()] } private: unordered_map hash vector nums }