LeetCode: Insert Delete GetRandom O(1) – Duplicates allowed Posted on January 16, 2018July 26, 2020 by braindenny Insert Delete GetRandom O(1) – Duplicates allowed Similar Problems: Max Stack CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #oodesign, #random 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(); Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: hashmap with set as value // https://code.dennyzhang.com/insert-delete-getrandom-o1-duplicates-allowed // Basic Ideas: hashmap + array // // Complexity: Time O(1), Space O(n) import "math/rand" type RandomizedCollection struct { // value to positions positions map[int]map[int]bool values []int } /** Initialize your data structure here. */ func Constructor() RandomizedCollection { return RandomizedCollection{positions:map[int]map[int]bool{}, values:[]int{}} } /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ func (this *RandomizedCollection) Insert(val int) bool { res := false if _, ok := this.positions[val]; !ok { this.positions[val] = map[int]bool{} res = true } this.positions[val][len(this.values)] = true this.values = append(this.values, val) return res } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ func (this *RandomizedCollection) Remove(val int) bool { // not found _, ok := this.positions[val] if !ok || len(this.positions[val]) == 0 { return false } // get one random position for the value of val pos := -1 for k, _ := range this.positions[val] { pos = k delete(this.positions[val], pos) break } // move last_element to val last_element := this.values[len(this.values)-1] this.values[pos] = last_element this.positions[last_element][pos] = true delete(this.positions[last_element], len(this.values)-1) // shorten array this.values = this.values[0:len(this.values)-1] return true } /** Get a random element from the collection. */ func (this *RandomizedCollection) GetRandom() int { index := rand.Intn(len(this.values)) return this.values[index] } /** * Your RandomizedCollection object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.Insert(val); * param_2 := obj.Remove(val); * param_3 := obj.GetRandom(); */ Post Views: 5