[Leetcode] 381. Insert Delete GetRandom O(1) - Duplicates allowed

381. Insert Delete GetRandom O(1) - Duplicates allowed
https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/
这个是上一道题升级版，难度也变成了hard，看来不可小觑！

看着和第一道题没啥区别，实际上区别大了！上一道题我们用hashset，这个东西key不能重复啊。我已开始想的是key指向的value换成list，list里面是一堆position，后来发现insert 还好办，delete不是常数复杂度啊，没办法，只能key里面再来一个hashMap了。坚持不看答案，以看答案为耻，恩！我发现自己太依赖答案了。从现在起，自己做，实在不行了再看答案。还有就是要强迫自己总结，不然都熊瞎子掰苞米了，简直了。这道题的考点上来说和上一道题一样的，都是hash map和list，目前看来是这样，只是更复杂了一点。仔细想了一下也不对啊，如果list of position的话也没什么不妥，反正，每个position的值一样，随便拿掉一个就行了嘛。最后看看list of posittion里面剩下东西没有，没剩下的话把那个hashMap entry 删除

以后每道题都自己做，有思路的就坚决不看答案。长时间没有思路的看思路，然后还是自己写出来，不然依赖答案太严重了！一定要独立！

这道题随机读取要于数字的个数成比例，这个好办，就把hashMap里面东西拿出来，然后放进一个list，然后和第一题一样随机读取就行了。但是这样有额外的空间要占用，所以，做完之后看看答案有没有啥好办法。

确实尝试独立来着，结果两天也没搞出来，基本思路对的，但是就是implement不出来。难度不高，但是需要炒鸡细心，我的错误是吧其中应该放在括号外面的一行放在了括号里面。导致错的很离谱。 用了一堆println 才搞定，最后两是print的函数，大家需要的话调用好了。

AC Solution：

public class RandomizedCollection {
 // Integer key is the value
    HashMap<Integer, HashSet<Integer>> map;
    List<Integer> list;
    int size;
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        map = new HashMap<Integer, HashSet<Integer>>();
        list = new ArrayList<Integer>();
        size = 0;
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        if(map.containsKey(val)){
            map.get(val).add(size);
            list.add(size++, val);
            return false;
        }else{
            HashSet<Integer> newSet = new HashSet<Integer>();
            newSet.add(size);
            map.put(val, newSet);
            list.add(size++, val);
        }
        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;
        }
        HashSet<Integer> valSet = map.get(val);
        System.out.println(valSet);
        int listPos = valSet.iterator().next();
        int tailKey = list.get(size -1);
        HashSet<Integer> tailKeySet = map.get(tailKey);
        list.set(listPos, tailKey);
        if(valSet.size() <= 1){
            map.remove(val);
        }
        else{
            valSet.remove(listPos);
        }     
        tailKeySet.add(listPos);
        tailKeySet.remove(size-1);
        list.remove(size-1);
        size--;
        return true;     
    }
    /** Get a random element from the collection. */
    public int getRandom() {
        Random rand = new Random();
        return list.get(rand.nextInt(size));
    }
    
    public void printList(){
        System.out.println("List:");
        System.out.println(list);
    }
    
    public void printMap(){
        System.out.println("Map:");
        System.out.println(map);
    }
}