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

time: all O(1)

space: O(1~n)

class RandomizedCollection {
    
    private List<Integer> nums;
    private Map<Integer, Set<Integer>> map; // use set to store multi indexs
    private Random rand;
    
    public RandomizedCollection() {
        nums = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        boolean result = !map.containsKey(val); // this is tricky...
        
        map.computeIfAbsent(val, k -> new HashSet<>());
        map.get(val).add(nums.size()); // add (val, num.size())
        nums.add(val); // add nums in list
        return result;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        
        Set<Integer> deleteIndexs = map.get(val);
        
        // if remove middle position in muti indexs(sets)
        if (!deleteIndexs.contains(nums.size()-1)) { // lastnum put into dele...
            int deleteIndex = deleteIndexs.iterator().next(); // get one of indexs from sets to delete 
            int lastNum = nums.get(nums.size()-1); // the last number
            
            nums.set(deleteIndex, lastNum);
            
            map.get(lastNum).remove(nums.size()-1); // remove origin index
            map.get(lastNum).add(deleteIndex); // change to deleteIndex
            map.get(val).remove(deleteIndex); // remove delete val
        }
        
        // if remove last position
        map.get(val).remove(nums.size()-1);// remove map(val, last position index)
        if (map.get(val).size() == 0) { // if set is empty, directly remove 
            map.remove(val);
        }
        nums.remove(nums.size()-1); // remove last num in list
        return true;
    }
    
    public int getRandom() {
        return nums.get(rand.nextInt(nums.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();
 */