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

Design a data structure that supports all following operations inaverage 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();

Thoughts:

1. nums: data lsit

2. indiecs: index reverse mapping: <val, i>

3. for add: check key is in the indices list set. if not put a new set in to val: <val, new set>; add i as current nums.size(), then add value to data array nums.

4. for remove: for check if the val is a valid key: if it is, retrieve the next index value for the val as iterator.next(), remove the index value from val entry. Then i is not at the end of the nums. Then fill the last element to the ith position in the nums list:

   1. retrieve the value from the last element in nums as "last"

   2. updating last's position entry record in set by first removing old index value then add value of position to be filled to the set

   3. remove the last element from the data nums.

   4. check the set in val becomes empty, if it is, remove the set entry in map.

Code: java

class RandomizedCollection {
    ArrayList<Integer> nums;
    HashMap<Integer, Set<Integer>> indices;
    java.util.Random rand; 
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        nums = new ArrayList<>();
        rand = new java.util.Random();
        indices = 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 = indices.containsKey(val);
        if(!contain) indices.put(val, new LinkedHashSet<>());
        indices.get(val).add(nums.size());
        nums.add(val);
        return !contain;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        boolean contain = indices.containsKey(val);
        if (!contain) return false;
        int i = indices.get(val).iterator().next();
        // remove from indices record
        indices.get(val).remove(i);

        // remove from nums data
        if(i < nums.size() -1){
            int last = nums.get(nums.size() -1);
            nums.set(i, last);
            // update last's record
            indices.get(last).remove(nums.size() - 1);
            indices.get(last).add(i);

        }
        nums.remove(nums.size() - 1); // remove last element
        // check set entry is empty()?
        if(indices.get(val).isEmpty()) indices.remove(val);
        return true;

    }

    /** Get a random element from the collection. */
    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();
 */