LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复（链表，哈希套哈希）

本文主要是介绍LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复（链表，哈希套哈希），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

思路：
这道题：“LeetCode380. 常数时间插入、删除和获取随机元素”的加强版。
同样的用 $v e c t o r$ 加哈希记录每个值的位置。因为可能出现重复的元素，所以我们用哈希套哈希，来记录这个值对应所有出现的位置。

class RandomizedCollection {
private:vector<int>vec;unordered_map<int,unordered_map<int,int>>vec_table;
public:/** Initialize your data structure here. */RandomizedCollection() {vec.clear();vec_table.clear();srand(time(NULL));}/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */bool insert(int val) {auto it = vec_table.find(val);bool flag = true;if(it != vec_table.end()) {flag = false;} vec.push_back(val);vec_table[val][vec.size() - 1] = 1;return flag;}/** Removes a value from the collection. Returns true if the collection contained the specified element. */bool remove(int val) {auto it = vec_table.find(val);if(it == vec_table.end()) return false;int pos = vec_table[val].begin() -> first;vec_table[val].erase(pos);if(vec_table[val].size() == 0) {vec_table.erase(val);}if(pos != vec.size() - 1) {swap(vec[pos],vec.back());vec_table[vec[pos]][pos] = 1;vec_table[vec[pos]].erase(vec.size() - 1);}vec.pop_back();return true;}/** Get a random element from the collection. */int getRandom() {int id = rand() % vec.size();return vec[id];}
};
/*** 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();*/