题目：设计一个数据结构，以平均时间复杂度O(1)支持以下操作。insert(val)：当元素val不存在时，将该项插入到集合中。remove(val)：当元素val存在时，从集合中移除该项。getRandom：随机返回现有集合中的一项。每个元素应该有相等的返回概率。设计一个平均O(1)时间支持所有后续操作的数据结构：从当前元素集中返回一个随机元素。每个元素必须具有相同的返回概率。示例//初始化一个空集合。RandomizedSetrandomSet=newRandomizedSet();//向集合中插入1。返回true表示成功插入1。randomSet.insert(1);//返回false，说明2不存在于集合中。randomSet.remove(2);//将2插入集合中。返回真。该集合现在包含[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)插入删除操作：可以从头设计哈希算法，也可以使用已经用高级编程语言设计好的哈希集/映射。要求是相同的概率随机返回元素：哈希集不能随机返回元素。可以使用数组等顺序存储，随机生成索引下标，返回对应的元素值。那么就需要使用hash映射来存储元素，key就是元素value，value就是辅助数组存储的索引下标值。插入操作是一个数组。hashmap的插入操作的难点在于删除操作。先删除hashmap中的键值对，再删除数组中的元素值，不能简单的赋一个不可能的值来误删，因为这种误删会导致数组变大，更大并破坏内存。代码：Java:classRandomizedSet{Listlist;Map地图；随机兰特；/**在这里初始化你的数据结构。*/publicRandomizedSet(){list=newArrayList();映射=新的HashMap();兰德=新的随机（）；}/***向集合中插入一个值。如果集合尚未包含指定元素，则返回true。*正常的插入操作*/publicbooleaninsert(intval){if(map.containsKey(val))returnfalse;map.put(val,list.size());//value表示存储在列表中的索引下标list.add(val);//添加到数组列表尾部returntrue;}/***从集合中删除一个值。如果集合包含指定元素，则返回true。**/publicbooleanremove(intval){if(!map.containsKey(val))//如果key在hashmap中不存在，则直接返回Falsereturnfalse;inttmp=list.get(list.size()-1);//暂存数组的最后一个元素值intindex=map.get(val);//获取列表数组list.set(index,tmp)中待删除元素对应的索引下标；//将列表中元素的值改为暂存数组的最后一位map.put(tmp,index);//更新hashmap中代表数组最后一位的键值对对应的索引下标为索引list.remove(list.size()-1);//删除数组的最后一位map.remove(val);//删除哈希映射中的键值对returntrue;}/**从集合中获取一个随机元素。*/publicintgetRandom(){returnlist.get(rand.nextInt(list.size()));//生成大小为[0,arraysize)的随机索引下标}}Python:fromrandomimportchoiceclassRandomizedSet:def__init__(self):"""在这里初始化你的数据结构。"""self.val_map=dict()self.val_list=list()definsert(self,val:int)->bool:"""向集合中插入一个值。如果集合尚未包含指定元素，则返回true。"""如果val不在self.val_map:self.val_map[val]=len(self.val_list)#value表示保存在val_list中的索引下标self.val_list.append(val)#添加到数组val_listtailreturnTruereturnFalsedefremove(self,val:int)->bool:"""从集合中删除一个值。如果集合包含指定元素，则返回true。"""ifvalinself.val_map:index=self.val_map[val]#获取list数组index中待删除元素对应的索引下标last_val=self.val_list[-1]#暂存数组最后一个元素值self.val_list[index]=last_val#将列表中元素的值改为暂存数组的最后一个值self.val_map[last_val]=index#更新表示数组最后一位的键值对对应的索引下标哈希映射到索引self.val_map.pop(val)#删除哈希映射中的键值对self.val_list.pop()#删除数组的最后一位returnTruereturnFalsedefgetRandom(self)->int:"""从集合中获取一个随机元素"""returnchoice(self.val_list)#返回数组中的一个随机元素欢迎关注WeChat_信公众号：爱写BUG
