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

CaesarChang张旭

发布于 2021-06-29 10:21:52

5730

发布于 2021-06-29 10:21:52

文章被收录于专栏：悟道

设计一个支持在平均时间复杂度 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()));
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/06/26 ，如有侵权请联系 cloudcommunity@tencent.com 删除

sql