Leetcode 380. O(1) 时间插入、删除和获取随机元素（DAY 157）---- LeetCode 精选 TOP 面试题

ゞ 浴缸里的玫瑰 2022-09-09 04:49 79阅读 0赞

文章目录

    • 原题题目
    • 代码实现（首刷自解）

原题题目

在这里插入图片描述

代码实现（首刷自解）

  1. class RandomizedSet { 
  2. public:
  3.     /** Initialize your data structure here. */
  4.     unordered_map<int,int> map;
  5.     vector<int> v;
  7.     RandomizedSet() { }
  9.     /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
  10.     bool insert(int val) { 
  11.         if(map.find(val) != map.end())  return false;
  12.         v.emplace_back(val);
  13.         map[val] = v.size()-1;
  14.         return true;
  15.     }
  17.     /** Removes a value from the set. Returns true if the set contained the specified element. */
  18.     bool remove(int val) { 
  19.         if(map.find(val) == map.end())  return false;
  20.         swap(v[map[val]],v[v.size()-1]);
  21.         v.pop_back();
  22.         map[v[map[val]]] = map[val];
  23.         map.erase(map.find(val));
  24.         return true;
  25.     }
  27.     /** Get a random element from the set. */
  28.     int getRandom() { 
  29.         int pos = rand()%v.size();
  30.         return v[pos];
  31.     }
  32. };
  34. /** * 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(); */

发表评论

表情：
评论列表 （有 0 条评论，79人围观）

还没有评论，来说两句吧...

相关阅读