第381题---Insert Delete getRandom O(1) duplicate

• 题意描述：实现一个类，对插入，删除，和取得随机数都是O(1),可以多次存入

• 思路：插入为1的map，list；删除为1的list，map；随机数， 数组；

  • 插入的过程：在map中判断是否存在val，如果存在（find），false；不存在，在map和vector中插入数字
  • 删除的过程：在map中判断是否存在val，如果不存在（find）， false；存在，交换元素在vector中位置，删除map和vector中位置
  • 取得随机数：直接返回rand % 范围的vector中位置的数

• 代码

  class RandomizedCollection {
  public:
      /** Initialize your data structure here. */
      RandomizedCollection() {
          
      }
      
      /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
      bool insert(int val) {
          bool res;
          if(m.find(val) == m.end())
              res = true;
          else
              res = false;
          nums.push_back(val);
          m[val].push_back(nums.size() - 1);
          return res;
      }
      
      /** Removes a value from the collection. Returns true if the collection contained the specified element. */
      bool remove(int val) {
          if(m.find(val) == m.end())
              return false;
          if(m[val].empty())
              return false;
              
          int remove_idx = m[val].back();
          int last = nums.size()-1;
          int last_val = nums[last];
          
          swap(nums[remove_idx], nums[last]);
          m[last_val].back() = remove_idx;
          
          m[val].pop_back();
          nums.pop_back();
          return true;
      }
      
      /** Get a random element from the collection. */
      int getRandom() {
          return nums[rand() % nums.size()];
      }
  private:
      vector<int> nums;
      unordered_map<int, vector<int>> m;
  };
  
  /**
   * Your RandomizedCollection object will be instantiated and called as such:
   * RandomizedCollection obj = new RandomizedCollection();
   * bool param_1 = obj.insert(val);
   * bool param_2 = obj.remove(val);
   * int param_3 = obj.getRandom();
   */