申请免费个人网站和域名,微信公司网站,网站建设的重要,县网站建设方案1. 题目
设计一个支持在平均 时间复杂度 O(1) 下#xff0c;执行以下操作的数据结构。
insert(val)#xff1a;当元素 val 不存在时#xff0c;向集合中插入该项。 remove(val)#xff1a;元素 val 存在时#xff0c;从集合中移除该项。 getRandom#xff1a;随机返回现…1. 题目
设计一个支持在平均 时间复杂度 O(1) 下执行以下操作的数据结构。
insert(val)当元素 val 不存在时向集合中插入该项。 remove(val)元素 val 存在时从集合中移除该项。 getRandom随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
来源力扣LeetCode 链接https://leetcode-cn.com/problems/insert-delete-getrandom-o1 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
哈希表 key存储数据value存储其在vector中的下标删除时先把vector尾部的数存到要删除的位置
class RandomizedSet {vectorint v;unordered_mapint,int m;
public:RandomizedSet() { }bool insert(int val) {if(m.find(val) m.end()){m[val] v.size();v.push_back(val);return true;}elsereturn false;}bool remove(int val) {if(m.find(val) m.end())return false;v[m[val]] v.back();m[v.back()] m[val];v.pop_back();m.erase(val);return true;}int getRandom() {if(v.size() 0)return -1;return v[rand() % v.size()];}
};
