Contents

# Problem

Design a data structure that supports all following operations in average O(1) time.

• `insert(val)`: Inserts an item val to the set if not already present.
• `remove(val)`: Removes an item val from the set if present.
• `getRandom`: Returns a random element from current set of elements. Each element must have the same probability of being returned.

## example 1

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 `````` ``````// Init an empty set. RandomizedSet randomSet = new RandomizedSet(); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomSet.insert(1); // Returns false as 2 does not exist in the set. randomSet.remove(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomSet.insert(2); // getRandom should return either 1 or 2 randomly. randomSet.getRandom(); // Removes 1 from the set, returns true. Set now contains [2]. randomSet.remove(1); // 2 was already in the set, so return false. randomSet.insert(2); // Since 2 is the only number in the set, getRandom always return 2. randomSet.getRandom(); ``````

# Solution

## HashMap + Array

 `````` 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 56 57 58 59 60 61 62 63 64 65 66 67 `````` ``````type RandomizedSet struct { M map[int]int A []int } /** Initialize your data structure here. */ func Constructor() RandomizedSet { rand.Seed(time.Now().UnixNano()) return RandomizedSet{ M: make(map[int]int,0), A: make([]int,0), } } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ func (this *RandomizedSet) Insert(val int) bool { if _, ok := this.M[val]; ok { return false } this.A = append(this.A, val) this.M[val] = len(this.A)-1 return true } /** Removes a value from the set. Returns true if the set contained the specified element. */ func (this *RandomizedSet) Remove(val int) bool { if _, ok := this.M[val]; !ok { return false } if len(this.A) == 1 { this.A = []int {} } else { z := this.A[len(this.A)-1] this.A[this.M[val]], this.A[len(this.A)-1] = this.A[len(this.A)-1], this.A[this.M[val]] this.M[z] = this.M[val] this.A = this.A[:len(this.A)-1] } delete(this.M, val) return true } /** Get a random element from the set. */ func (this *RandomizedSet) GetRandom() int { k := rand.Intn(len(this.A)) return this.A[k] } /** * Your RandomizedSet object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.Insert(val); * param_2 := obj.Remove(val); * param_3 := obj.GetRandom(); */ ``````