Cacher is the code snippet organizer for pro developers

/*
LinkedHashSet中不能有相同元素，可以有一个Null元素，元素严格按照放入的顺序排列
添加、删除操作时间复杂度都是O(1)
    set.remove(Object o); o是指具体的元素value
    int remove_idx = idx.get(val).iterator().next();
*/

class RandomizedCollection {
    ArrayList<Integer> lst;
    HashMap<Integer, Set<Integer>> idx;
    java.util.Random rand = new java.util.Random();
    
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        lst = new ArrayList<Integer>();
	    idx = new HashMap<Integer, Set<Integer>>();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        if (!idx.containsKey(val)) 
            idx.put(val, new LinkedHashSet<Integer>());
        idx.get(val).add(lst.size());
        lst.add(val);
        return idx.get(val).size() == 1;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        //⭐️已创建过但被remove为空了也要考虑
        if (!idx.containsKey(val) || idx.get(val).size() == 0) 
            return false;
	    int remove_idx = idx.get(val).iterator().next();
        idx.get(val).remove(remove_idx);
        int last = lst.get(lst.size() - 1);
        lst.set(remove_idx, last);
        idx.get(last).add(remove_idx);
        idx.get(last).remove(lst.size() - 1);  //the index of last element
	    lst.remove(lst.size() - 1);
        return true;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        return lst.get(rand.nextInt(lst.size()));
    }
}