Leetcode 380. 常数时间插入、删除和获取随机元素

题目

设计一个支持在平均 时间复杂度 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();

题解

我们使用一个数组存储所有可能的数。当添加数时，把它放到尾部就行了；对于删除数，因为我们要实现O(1)，而对于数组，只有删除最后一个元素才是O(1)，因此我们不妨让最后一个元素和要删除的元素进行替换，删除最后一个元素即可。由删除操作可知，我们要找到删除元素的位置，为了实现O(1)，我们用一个哈希表记录数字在数组中的位置。随机取数就用random()函数%数组大小 详细过程见代码

代码

class RandomizedSet { public: vector<int> nums; unordered_map<int,int> numIndex; int size; /** Initialize your data structure here. */ RandomizedSet() { size = 0; } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ bool insert(int val) { if(numIndex.count(val) == 1) return false; //不能重复插入数字 nums.push_back(val); numIndex[val] = size; size++; return true; } /** Removes a value from the set. Returns true if the set contained the specified element. */ bool remove(int val) { if(numIndex.count(val) == 0) return false; int last = nums.back(); nums[numIndex[val]] = last; numIndex[last] = numIndex[val]; //删除的数和最后一个数进行替换 nums.pop_back(); numIndex.erase(val); size--; return true; } /** Get a random element from the set. */ int getRandom() { return nums[random() % size]; } }; /** * 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） 链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。