381.常数时间插入、删除和获取随机元素 - 允许重复.md

381.O(1) 时间插入、删除和获取随机元素 - 允许重复

题目

设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。

注意: 允许出现重复元素。

• insert(val)：向集合中插入元素 val。
• remove(val)：当 val 存在时，从集合中移除一个 val。
• getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

示例：

// 初始化一个空的集合。
RandomizedCollection collection = new RandomizedCollection();

// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);

// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(1);

// 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。
collection.insert(2);

// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。
collection.getRandom();

// 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。
collection.remove(1);

// getRandom 应有相同概率返回 1 和 2 。
collection.getRandom();

方法

remove操作让我们用O(1)的时间复杂度删除给定的val，但删除前，我们需要先找到val。因此考虑用O(1)的时间复杂度来进行查找，有两种方法：哈希表和数组（用索引实现O(1))

但是用数组(或列表)的话，查找操作是O(1)，但删除操作并不是O(1)的，因为删除一个元素往往意味着要移动其他元素。因此我们可以每次删除一个元素val时，都将这个元素和列表末尾元素交换，再删除末尾，这样也就相当于删除元素val了。

这样一来，我们同时就需要一个哈希表，来将val与其下标的关系记录下来。

• 删除操作：通过哈希表找到val的一个下标i，先将数组i位置的元素和尾位置的元素交换后删除nums尾部。再更新尾位置元素和i位置元素在哈希表中对应的下标。
• 插入操作：插入元素时，直接将val插入nums的末尾，并更新val在哈希表中对应的下标。
• getRandom操作：随机生成一个位置索引,返回这个索引对应的值

class RandomizedCollection {
    List<Integer> nums;
    Map<Integer, Set<Integer>> map;
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        nums = new ArrayList<>();
        map = new HashMap<>();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        //直接将val插入到列表末尾，并更新val在哈希表中对应的下标
        if(map.containsKey(val)){
            nums.add(val);
            map.get(val).add(nums.size() - 1);
            return false;
        }
        else{
            nums.add(val);
            Set<Integer> set = new HashSet<>();
            set.add(nums.size() - 1);
            map.put(val, set);
            return true;
        }
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val))
            return false;
        else{
            //先更新val在哈希表中对应的索引
            Set<Integer> set = map.get(val);
            int i =set.iterator().next();
            set.remove(i);
            if(set.size() ==0){
                map.remove(val);
            }
            //再将val与尾元素交换，删除尾元素，更新尾元素在哈希表中对应的索引
            int lastNumIndex = nums.size()-1;
            if(i == lastNumIndex){
                nums.remove(lastNumIndex);
            }else{
                int lastNum = nums.remove(lastNumIndex);
                nums.set(i,lastNum);
                map.get(lastNum).remove(lastNumIndex);
                map.get(lastNum).add(i);
            }
            return true;
        }
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        //随机生成一个索引,返回这个索引对应的值
        int index = (int)(Math.random() * nums.size());
        return nums.get(index);
    }
}