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

Published on with 0 views and 0 comments

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.

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();
``````

go：

``````type RandomizedCollection struct {
m map[int][]int
arr []*node
}

type node struct {
val int
index int // map value中的index
}

/** Initialize your data structure here. */
func Constructor() RandomizedCollection {
return RandomizedCollection {
m: make(map[int][]int),
arr:make([]*node, 0),
}
}

/** 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 {
indexs, ok := this.m[val]
if !ok {
n := &node{val:val, index:0}
this.m[val] = []int{len(this.arr)}
this.arr = append(this.arr, n)
return true
} else {
n := &node{val:val, index:len(indexs)}
this.m[val] = append(indexs, len(this.arr))
this.arr = append(this.arr, n)
return false
}
return true
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
func (this *RandomizedCollection) Remove(val int) bool {
targetIndexs, ok := this.m[val]
if !ok || len(targetIndexs) == 0 {
return false
}

// 1. 取出targetIndexs最后一个索引，根据这个索引找到要删除的元素在数组中的位置
tIndex := targetIndexs[len(targetIndexs)-1]

// 2. 取出数组中的最后一个元素
lastNode := this.arr[len(this.arr)-1]

// 3. 把最后一个元素交换到tIndex上,然后删除arr最后一个元素
this.arr[tIndex] = lastNode
this.arr = this.arr[:len(this.arr)-1]

// 4. 更新lastNode在map的value数组中的位置
lastIndexs, _ := this.m[lastNode.val]
lastIndexs[lastNode.index] = tIndex

// 5. 删除目标元素在map的value数组中的最后一位
targetIndexs = targetIndexs[:len(targetIndexs)-1]
this.m[val] = targetIndexs

return true
}

/** Get a random element from the collection. */
func (this *RandomizedCollection) GetRandom() int {
r := rand.Int31n(int32(len(this.arr)))
return this.arr[int(r)].val
}

/**
* 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();
*/
``````