题目

Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
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.

分析

这题和上题差不多，不过是允许插入重复数字，不过需要注意的是每次删除还是删除一个。
这题可以将原来的map<Integer, Integer> 换为 map<Integer, Set<Integer>>来记录元素出现的位置，其余的稍微改动一下即可。
需要注意的是，如果set为空了，map要删除这个元素的记录。

代码

class RandomizedCollection {
    private List<Integer> list;
    private Map<Integer, Set<Integer>> map;
    private java.util.Random rand = new java.util.Random();
    
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        list = 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) {
        boolean contain = map.containsKey(val);
        if(!contain) map.put(val, new LinedHashSet<Integer>());
        map.get(val).add(list.size());
        list.add(val);
        return !contain;
    }
    
    /** 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;
        Set<Integer> set = map.get(val);  //indexes
        int index = set.iterator().next();
        set.remove(index);
        if(index != list.size() - 1){
            int last = list.get(list.size() - 1);  //move last value to safe place
            map.get(last).remove(list.size() - 1);  //update map
            map.get(last).add(index);   
            list.set(index, last);  //update list
        }
        list.remove(list.size() - 1);
        
        if(set.isEmpty()){  //这里不可少
            map.remove(val);
        }
        
        return true;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

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