381. Insert Delete GetRandom O(1) - Duplicates allowed
https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/
---
Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.insert(val): Inserts an item val to the collection.remove(val): Removes an item val from the collection if present.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();
Related problems
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class RandomizedCollection { | |
| // Actual storage of val, return entry from a random index | |
| List<Integer> list; | |
| // Map the value to indices of value in List | |
| Map<Integer, Set<Integer>> map; | |
| // Random number generator, create it once for the class | |
| Random random; | |
| /** Initialize your data structure here. */ | |
| public RandomizedCollection() { | |
| list = new ArrayList<Integer>(); | |
| map = new HashMap<Integer, Set<Integer>>(); | |
| random = new Random(); | |
| } | |
| /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ | |
| public boolean insert(int val) { | |
| // Initialize empty set | |
| map.putIfAbsent(val, new HashSet<Integer>()); | |
| // Add last index for the new val | |
| map.get(val).add(list.size()); | |
| list.add(val); | |
| // True if val is added for first time | |
| return map.get(val).size() == 1; | |
| } | |
| /** Removes a value from the collection. Returns true if the collection contained the specified element. */ | |
| public boolean remove(int val) { | |
| if (!map.containsKey(val) || map.get(val).size() == 0) { | |
| return false; | |
| } | |
| // Fetch index of val to remove | |
| int indexToRemove = map.get(val).iterator().next(); | |
| // Fetch last value from list | |
| int last = list.get(list.size() - 1); | |
| // Add the new position to last value | |
| map.get(last).add(indexToRemove); | |
| // *** Corner case *** Move the last value to firstIndex only if not duplicate | |
| if (last != val) { | |
| // Copy last value to position of value to be removed | |
| list.set(indexToRemove, last); | |
| map.get(val).remove(indexToRemove); | |
| } | |
| // Remove the last value from end of list | |
| map.get(last).remove(list.size() - 1); | |
| list.remove(list.size() - 1); | |
| return true; | |
| } | |
| /** Get a random element from the collection. */ | |
| public int getRandom() { | |
| return list.get(random.nextInt(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(); | |
| */ |
