LeetCode380 常数时间插入、删除和获取随机元素
程序员文章站
2022-06-29 21:30:36
LeetCode380 常数时间插入、删除和获取随机元素 题目要求 设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。 insert(val):当元素 val 不存在时,向集合中插入该项。 remove(val):元素 val 存在时,从集合中移除该项。 getRandom:随机 ......
leetcode380 常数时间插入、删除和获取随机元素
题目要求
设计一个支持在平均 时间复杂度 o(1) 下,执行以下操作的数据结构。
insert(val):当元素 val 不存在时,向集合中插入该项。
remove(val):元素 val 存在时,从集合中移除该项。
getrandom:随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :
// 初始化一个空的集合。 randomizedset randomset = new randomizedset(); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。 randomset.insert(1); // 返回 false ,表示集合中不存在 2 。 randomset.remove(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。 randomset.insert(2); // getrandom 应随机返回 1 或 2 。 randomset.getrandom(); // 从集合中移除 1 ,返回 true 。集合现在包含 [2] 。 randomset.remove(1); // 2 已在集合中,所以返回 false 。 randomset.insert(2); // 由于 2 是集合中唯一的数字,getrandom 总是返回 2 。 randomset.getrandom();
分析:
查找最快的数据结构为列表或者hash表,分别按照角标或者内容查找。
删除元素hash表时间复杂度为常数时间,但是列表则为线性时间,本题需要做特殊处理,对于要删除的元素采用交换到末尾的策略,然后删除末尾元素再更新对应的hash表。
代码:
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(hashmap.find(val) != hashmap.end()) { return false; } vec.push_back(val); hashmap[val] = vec.size()-1; return true; } /** removes a value from the set. returns true if the set contained the specified element. */ bool remove(int val) { if(hashmap.find(val) == hashmap.end()) { return false; } int index = hashmap.find(val) -> second; if(index == vec.size() - 1) { vec.pop_back(); hashmap.erase(val); }else { hashmap[vec[vec.size()-1]] = index; swap(vec[index], vec[vec.size() - 1]); vec.pop_back(); hashmap.erase(val); } return true; } /** get a random element from the set. */ int getrandom() { if(!vec.size()) { return -1; } int index = rand() % vec.size(); return vec[index]; } private: unordered_map<int, int> hashmap; vector<int> vec; }; /** * 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(); */
上一篇: 就需要从头来过
推荐阅读
-
LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复(vector + 哈希)
-
LeetCode380 常数时间插入、删除和获取随机元素
-
LeetCode(380 & 381):O(1) 时间插入、删除和获取随机元素 Insert Delete GetRandom O(1)(Java)
-
[LeetCode] 381. Insert Delete GetRandom O(1) - Duplicates allowed 插入删除和获得随机数O(1)时间 - 允许重复...
-
380. Insert Delete GetRandom O(1) O(1) 时间插入、删除和获取随机元素(Medium)
-
381 Insert Delete GetRandom O(1) - Duplicates allowed O(1) 时间插入、删除和获取随机元素 - 允许重复...
-
【LeetCode】 381. Insert Delete GetRandom O(1) - Duplicates allowed 插入、删除和获取随机元素 - 允许重复(Hard)(JAVA)
-
leetcode 380. insert-delete-getrandom-o1 常数时间插入、删除和获取随机元素 python3
-
380. Insert Delete GetRandom O(1) O(1)时间的插入、删除和随机取元素
-
380.Insert Delete GetRandom O(1) 常数时间内插入删除和获得随机数