面试经典150题——O(1) 时间插入、删除和获取随机元素

面试经典150题 day12

- - 题目来源
  - 我的题解
  - - 方法一 ArrayList+不满足时间复杂度为O(1)
    - 方法二 ArrayList+HashMap

题目来源

力扣每日一题；题序：380

我的题解

方法一 ArrayList+不满足时间复杂度为O(1)

直接使用ArrayList存储

时间复杂度：
insert：O(n)。contains方法需要遍历整个数组，并且底层存在扩容
remove：O(n)
getRandom：O(1)。
空间复杂度：O(1)

class RandomizedSet {

  List<Integer> list = null;
  int len = 0;

  public RandomizedSet() {
    list = new ArrayList<>();
  }

  public boolean insert(int val) {
    if (list.contains(val)) return false;
    list.add(val);
    len++;
    return true;
  }

  public boolean remove(int val) {
    if (list.contains(val)) {
      list.remove((Integer) val);
      len--;
      return true;
    }
    return false;
  }

  public int getRandom() {
    Random r = new Random();
    int index = r.nextInt(this.len);
    return list.get(index);
  }
}

方法二 ArrayList+HashMap

ArrayList用于实现随机查询，并使用HashMap记录每个元素对应数组的下标位置，通过在数组末尾添加元素，和使用末尾元素替换删除元素的操作实现O(1)级别的删除和插入（注意：没有考虑底层数组扩容）

时间复杂度：
insert：O(1)。不考虑底层数组扩容
remove：O(1)
getRandom：O(1)。
空间复杂度：O(1)

class RandomizedSet {
    Map<Integer,Integer>  idx;
    List<Integer> ele;
    Random r;
    public RandomizedSet() {
        ele=new ArrayList<>();
        idx=new HashMap<>();
        r=new Random();
    }
    
    public boolean insert(int val) {
        if(idx.containsKey(val))
            return false;
        ele.add(val);
        idx.put(val,ele.size()-1);
        return true;
    }
    
    public boolean remove(int val) {
        if(!idx.containsKey(val))
            return false;
        int index=idx.get(val);
        int t=ele.get(ele.size()-1);
        idx.put(t,index);
        ele.set(index,t);
        idx.remove(val);
        ele.remove(ele.size()-1);
        return true;
    }
    
    public int getRandom() {
        int index=r.nextInt(idx.size());
        return ele.get(index);
    }
}