【LeetCode】 381. Insert Delete GetRandom O(1) - Duplicates allowed 插入、删除和获取随机元素 - 允许重复（Hard）（JAVA）

【LeetCode】 381. Insert Delete GetRandom O(1) - Duplicates allowed O(1) 时间插入、删除和获取随机元素 - 允许重复（Hard）（JAVA）

题目地址: https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

题目描述：

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

题目大意

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

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

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

解题方法

题目最大的难度在于插入、删除和随机获取都要是 O(1) 的时间复杂度，而且还有重复的元素

1. 如果没有重复的元素，直接存入 Map 就行了
2. 但是现在有重复的元素，我们只能存入 List 当中了，获取和插入都是 O(1) 的时间复杂度
3. 现在的问题是怎么解决删除元素可以 O(1) 的时间复杂度：把元素 val 对应的 index 存入 Map 当中
4. 因为插入和随机获取都是随机的，不要求和加入的顺序相同，所以删除的时候可以毫无顾虑，把 index 的元素删了，再把最后一个元素放到 index ，再把最后一个元素删了即可（要考虑 index 就是最后一个元素）

class RandomizedCollection {
    List<Integer> list = new ArrayList<>();
    Map<Integer, List<Integer>> map = new HashMap();

    /** Initialize your data structure here. */
    public RandomizedCollection() {

    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        list.add(val);
        List<Integer> temp = map.get(val);
        boolean flag = false;
        if (temp == null) {
            temp = new ArrayList<>();
            map.put(val, temp);
            flag = true;
        }
        temp.add(list.size() - 1);
        return flag;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        List<Integer> temp = map.get(val);
        if (temp == null) return false;
        int cur = temp.remove(0);
        int lastNum = list.get(list.size() - 1);
        list.set(cur, lastNum);
        temp = map.get(lastNum);
        temp.remove(new Integer(list.size() - 1));
        if (cur < list.size() - 1) temp.add(cur);
        if (map.get(val).size() == 0) map.remove(val);
        list.remove(list.size() - 1);
        return true;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        Random r = new Random();
        return list.get(r.nextInt(list.size()));
    }
}

执行用时：12 ms, 在所有 Java 提交中击败了 97.12% 的用户
内存消耗：42.4 MB, 在所有 Java 提交中击败了 98.85% 的用户