LeetCode - 380 O(1) 时间插入、删除和获取随机元素 （设计 哈希表+数组）

哈希表+list

class RandomizedSet {
    
    //将值放入list中 为了可以随机取数
    private List<Integer> list;
    //map的key是值 map的val是 值在list中的位置
    //为了方便在o(1)时间内 插入删除值
    private Map<Integer,Integer> map;
    public RandomizedSet() {
    
        list = new ArrayList<>();
        map = new HashMap<>();
    }
    
    public boolean insert(int val) {
    
          //如果该值已经存在了
          if(map.containsKey(val) == true)
            return false;
          else{
    
            //新添加值的index
            int index = list.size();
            //添加至list
            list.add(val);
            //添加至map
            map.put(val,index);
            return true;
          }
    }
    
    public boolean remove(int val) {
    
        //val不存在 删除失败
        if(map.containsKey(val) == false)
           return false;
        else{
    
           //list最后一个数的下标
         int lasti = list.size()-1;
         //list最后一个数的值
         int lastv = list.get(lasti);
         //val 在list中的下标
         int vali = map.get(val);
         //将list的最后一个数放在val在list的位置上
         list.set(vali,lastv);
         //修改list的最后一个数在map中的下标
         map.put(lastv,vali);
         //删除list中的最后一个数
         list.remove(lasti);
         //在map中删除val
         map.remove(val);
         return true;
        }
        
    }
    
    public int getRandom() {
    
        int n = list.size();
        //产生0 - n-1范围的随机整数
        return list.get((int)(Math.random()*n));
    }
}

/** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet obj = new RandomizedSet(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */