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

小咪咪 2022-10-10 06:01 64阅读 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]

  1. class RandomizedSet {
  2.     Set<Integer> set;
  3.     Random random=new Random();
  5.     public RandomizedSet() {
  6.        set=new HashSet();
  7.     }
  9.     public boolean insert(int val) {
  10.         if(!set.contains(val)){
  11.             set.add(val);
  12.             return true;
  13.         }
  14.         return  false;
  15.     }
  17.     public boolean remove(int val) {
  18.         if(set.contains(val)){
  19.             set.remove(val);
  20.             return true;
  21.         }
  22.         return false;
  23.     }
  25.     public int getRandom() {
  26.         Iterator<Integer> iter=set.iterator();
  27.         List<Integer> list=new ArrayList();
  28.         while(iter.hasNext()){
  29.             list.add(iter.next());
  30.         }
  31.         return list.get(random.nextInt(list.size()));
  32.     }
  33. }

发表评论

表情：
评论列表 （有 0 条评论，64人围观）

还没有评论，来说两句吧...

相关阅读