第380题---Insert Delete getRandom O(1)

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

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

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

• 代码实现

  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(m.find(val) != m.end())
              return false;
          nums.push_back(val);
          m[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(m.find(val) == m.end())
              return false;
          // 交换查找元素和最后一个元素的位置
          int last = nums.back();
          m[last] = m[val];
          nums[m[val]] = last;
          // 删除最后一个元素，和map中的元素
          nums.pop_back();
          m.erase(val);
          return true;
      }
      
      /** Get a random element from the set. */
      int getRandom() {
          return nums[rand() % nums.size()];
      }
      
  private:
      vector<int> nums;
      unordered_map<int, int> m;
  };
  
  /**
   * Your RandomizedSet object will be instantiated and called as such:
   * RandomizedSet obj = new RandomizedSet();
   * bool param_1 = obj.insert(val);
   * bool param_2 = obj.remove(val);
   * int param_3 = obj.getRandom();
   */