Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/381.html
381. Insert Delete GetRandom O(1) - 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();
@tag-array
Algorithm
For the insert()
function, we add the position of the number to be inserted in nums to the end of the m[val]
array, and then add val to the end of the array nums.
We judge whether there is a duplication as long as the m[val]
array has only one value of val just added or there are multiple values.
The remove()
function is the difficulty of this problem. First, let’s see if there is a val in the HashMap, and if not, return false directly.
Then we take the tail element of nums, and update the last position in the position array of the tail element HashMap to the tail element of m[val]
, so that we can delete the tail element of m[val]
. If m[val]
there is only one element, then we delete this mapping directly. Then delete the tail element in the nums array and assign the tail element to the position of val.
- Note that we need to use a heap instead of a normal vector array when building the mapping of HashMap
We use the priority queue to automatically sort all the coordinates of the same number, and move out the coordinates of the largest position each time.
Code
-
public class Insert_Delete_GetRandom_O_1_Duplicates_allowed { // https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/solution/ public class RandomizedCollection_official { ArrayList<Integer> list; HashMap<Integer, Set<Integer>> map; java.util.Random rand = new java.util.Random(); /** Initialize your data structure here. */ public RandomizedCollection_official() { list = new ArrayList<Integer>(); map = 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 (!map.containsKey(val)) map.put(val, new LinkedHashSet<Integer>()); map.get(val).add(list.size()); list.add(val); 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; int locToRemove = map.get(val).iterator().next(); map.get(val).remove(locToRemove); int last = list.get(list.size() - 1); list.set(locToRemove, last); map.get(last).add(locToRemove); 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(rand.nextInt(list.size())); } } // official solution is better class RandomizedCollection_unnecessary_ifLogic { private List<Integer> list; // hold list private Map<Integer, LinkedHashSet<Integer>> map; // val -> list of indexes Random random; public RandomizedCollection() { list = new ArrayList<>(); map = new HashMap<>(); random = new Random(); } public boolean insert(int val) { boolean ans = !map.containsKey(val); int loc = list.size(); list.add(val); LinkedHashSet<Integer> indices = map.getOrDefault(val, new LinkedHashSet<>()); indices.add(loc); map.put(val, indices); return ans; } public boolean remove(int val) { if (!map.containsKey(val) || map.get(val).isEmpty()) { return false; } // Get loc of the val to be removed int locToRemove = map.get(val).iterator().next(); // Set iterator if (locToRemove < list.size() - 1) { // if not last index, then swap to last index // Get the number to be swapped int numToSwap = list.get(list.size() - 1); // Put the tail number to the location to be removed list.set(locToRemove, numToSwap); map.get(numToSwap).add(locToRemove); // Update the loc // @note: when swap two are the same val // [2,1,1] => remove(1) if (map.get(numToSwap).contains(list.size() - 1)) { // undo above "map.get(numToSwap).add(locToRemove);" , if it's the last index // remove the same duplicate map.get(numToSwap).remove(list.size() - 1); } } // Remove the val in Set map.get(val).remove(locToRemove); // Remove the val list.remove(list.size() - 1); return true; } /** Get a random element from the collection. */ public int getRandom() { int loc = random.nextInt(list.size()); return list.get(loc); } } /** * 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(); */ }
-
class RandomizedCollection { public: RandomizedCollection() {} bool insert(int val) { m[val].insert(nums.size()); nums.push_back(val); return m[val].size() == 1; } bool remove(int val) { if (m[val].empty()) return false; int idx = *m[val].begin(); m[val].erase(idx); if (nums.size() - 1 != idx) { int t = nums.back(); nums[idx] = t; m[t].erase(nums.size() - 1); m[t].insert(idx); } nums.pop_back(); return true; } int getRandom() { return nums[rand() % nums.size()]; } private: vector<int> nums; unordered_map<int, unordered_set<int>> m; };
-
from collections import defaultdict from random import choice class RandomizedCollection: def __init__(self): """ Initialize your data structure here. """ self.lst = [] self.idx = defaultdict(set) def insert(self, val: int) -> bool: """ Inserts a value to the collection. Returns true if the collection did not already contain the specified element. """ self.idx[val].add(len(self.lst)) self.lst.append(val) return len(self.idx[val]) == 1 ''' >>> a = set([1,1,2,3]) >>> a {1, 2, 3} >>> a.pop() 1 >>> a {2, 3} ''' def remove(self, val: int) -> bool: """ Removes a value from the collection. Returns true if the collection contained the specified element. """ if not self.idx[val]: return False remove_index, last = self.idx[val].pop(), self.lst[-1] # pop() on a set self.lst[remove_index] = last self.idx[last].add(remove_index) self.idx[last].discard(len(self.lst) - 1) self.lst.pop() return True def getRandom(self) -> int: """ Get a random element from the collection. """ return choice(self.lst) # Your RandomizedCollection object will be instantiated and called as such: # obj = RandomizedCollection() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom() ############ class RandomizedCollection(object): def __init__(self): """ Initialize your data structure here. """ self.dOfd = collections.defaultdict(dict) self.d = collections.defaultdict(list) self.a = [] def insert(self, val): """ Inserts a value to the collection. Returns true if the collection did not already contain the specified element. :type val: int :rtype: bool """ self.d[val].append(len(self.a)) self.dOfd[val][len(self.a)] = len(self.d[val]) - 1 self.a.append(val) return len(self.d[val]) == 1 def remove(self, val): """ Removes a value from the collection. Returns true if the collection contained the specified element. :type val: int :rtype: bool """ dd = self.dOfd a = self.a d = self.d if not d[val]: return False idx = d[val][-1] a[idx] = a[-1] idxInDForLast = dd[a[-1]][len(a) - 1] d[a[-1]][idxInDForLast] = idx dd[a[-1]][idx] = idxInDForLast # del dd[val][idx] del dd[a[-1]][len(a) - 1] d[val].pop() a.pop() return True def getRandom(self): """ Get a random element from the collection. :rtype: int """ return self.a[random.randrange(0, len(self.a))] # Your RandomizedCollection object will be instantiated and called as such: # obj = RandomizedCollection() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom()