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

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

Hard

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

class RandomizedCollection { ArrayList<Integer> list; HashMap<Integer, LinkedHashSet<Integer>> valToInd; /** Initialize your data structure here. */ public RandomizedCollection() { list = new ArrayList<>(); valToInd = 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 contains = valToInd.containsKey(val); if(!contains) valToInd.put(val, new LinkedHashSet<Integer>()); valToInd.get(val).add(list.size()); list.add(val); return !contains; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ public boolean remove(int val) { if(!valToInd.containsKey(val)) return false; int iEnd = list.size()-1; int vEnd = list.get(iEnd); int iToBeRemoved; if(val==vEnd) { iToBeRemoved = iEnd; }else{ iToBeRemoved = valToInd.get(val).iterator().next(); Collections.swap(list, iToBeRemoved, iEnd); valToInd.get(vEnd).remove(iEnd); valToInd.get(vEnd).add(iToBeRemoved); } valToInd.get(val).remove(iToBeRemoved); list.remove(iEnd); if(valToInd.get(val).size()==0) valToInd.remove(val); return true; } /** Get a random element from the collection. */ public int getRandom() { return list.get((int) (Math.random()*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(); */