链接381. O(1) 时间插入、删除和获取随机元素 - 允许重复题解class RandomizedCollection { public: RandomizedCollection() {} bool insert(int val) { bool result _num2index.find(val) _num2index.end(); _nums.push_back(val); _num2index[val].insert(_nums.size() - 1); return result; } bool remove(int val) { auto ite _num2index.find(val); if (ite _num2index.end()) { return false; } int del_index *(ite-second.begin()); int last_index _nums.size() - 1; /*判断最后一个数字是不是要删除的数字*/ if (val _nums.back()) { // 删除索引 _num2index[val].erase(last_index); // 如果索引为空直接删除 if (_num2index[val].size() 0) { _num2index.erase(val); } // 最后一个数字弹出 _nums.pop_back(); return true; } // 更新数字 _nums[del_index] _nums.back(); // 删除老位置 _num2index[_nums.back()].erase(last_index); // 插入新位置 _num2index[_nums.back()].insert(del_index); // 删除元素的索引 _num2index[val].erase(del_index); // 为空删除 if (_num2index[val].empty()) { _num2index.erase(val); } // 弹出最后一个元素 _nums.pop_back(); return true; } int getRandom() { if (_nums.size() 0) { return 0; } return _nums[random() % _nums.size()]; } private: vectorint _nums; unordered_mapint, unordered_setint _num2index; }; /** * 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(); */class RandomizedCollection { private: std::unordered_mapint, std::unordered_setint tabel_; std::vectorint nums_; public: /** Initialize your data structure here. */ RandomizedCollection() { tabel_.clear(); nums_.clear(); } /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ bool insert(int val) { bool ret tabel_.find(val) tabel_.end(); nums_.push_back(val); tabel_[val].insert(nums_.size()-1); return ret; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ bool remove(int val) { // 判断val是否存储 if(tabel_.find(val) tabel_.end()) { return false; } // 找到val存在的下标 int index *(tabel_[val].begin()); // 将数组中最后元素替换index位置 nums_[index] nums_.back(); // 将index从table中删除 tabel_[val].erase(index); // 将nums_.back()元素的下标也删除 tabel_[nums_.back()].erase(nums_.size()-1); // 更新nums_.back()的下标 if(index nums_.size()-1) { tabel_[nums_.back()].insert(index); } // 如果index的table全部删除了删除将val从table if(tabel_[val].size() 0) { tabel_.erase(val); } nums_.pop_back(); return true; } /** Get a random element from the collection. */ int getRandom() { return nums_[random()%nums_.size()]; } }; /** * * 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(); * */