380. O(1) 时间插入、删除和获取随机元素

小咪咪 2022-10-10 06:01 49阅读 0赞

> 设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
> 
> insert(val)：当元素 val 不存在时，向集合中插入该项。  
> remove(val)：元素 val 存在时，从集合中移除该项。  
> getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
> 
> 输入:\["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"\]  
> \[\[\],\[1\],\[2\],\[2\],\[\],\[1\],\[2\],\[\]\]
> 
> 输出:\[null,true,false,true,2,true,false,2\]

class RandomizedSet {
        Set<Integer> set;
        Random random=new Random();
    
        public RandomizedSet() {
           set=new HashSet();
        }
        
        public boolean insert(int val) {
            if(!set.contains(val)){
                set.add(val);
                return true;
            }
            return  false;
        }
        
        public boolean remove(int val) {
            if(set.contains(val)){
                set.remove(val);
                return true;
            }
            return false;
        }
        
        public int getRandom() {
            Iterator<Integer> iter=set.iterator();
            List<Integer> list=new ArrayList();
            while(iter.hasNext()){
                list.add(iter.next());
            }
            return list.get(random.nextInt(list.size()));
        }
    }