本文主要是介绍力扣380. O(1) 时间插入、删除和获取随机元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
哈希表 + 变长数组
- 思路：
- O(1) 插入、删除想到的是哈希表，但是不能 O(1) 获取随机元素；
- 变长数组可以 O(1) 获取随机元素但是不能 O(1) 插入和删除；
- 需要结合这两个数据结构，将数据存放在 vector 中，用哈希表来记录其索引；
class RandomizedSet {
public:RandomizedSet() {srand((unsigned)time(NULL));}bool insert(int val) {if (idx_.count(val)) {return false;}int index = data_.size();data_.emplace_back(val);idx_[val] = index;return true;}bool remove(int val) {if (idx_.count(val) == 0) {return false;}int index = idx_[val];int last_val = data_.back();data_[index] = last_val;idx_[last_val] = index;data_.pop_back();idx_.erase(val);return true;}int getRandom() {int rndIdx = rand() % data_.size();return data_[rndIdx];}private:std::vector<int> data_;std::unordered_map<int, int> idx_;
};/*** 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();*/这篇关于力扣380. O(1) 时间插入、删除和获取随机元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
