-
Notifications
You must be signed in to change notification settings - Fork 0
/
solution.go
61 lines (54 loc) · 1.28 KB
/
solution.go
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
package insert_delete_getrandom_o1_duplicates_allowed
import "math/rand"
type RandomizedCollection struct {
indexMap map[int]map[int]struct{}
data []int
}
func Constructor() RandomizedCollection {
return RandomizedCollection{
indexMap: make(map[int]map[int]struct{}),
}
}
func (rc *RandomizedCollection) Insert(value int) bool {
index := len(rc.data)
rc.data = append(rc.data, value)
if indexes, exists := rc.indexMap[value]; exists {
indexes[index] = struct{}{}
return false
} else {
indexes := map[int]struct{}{index: {}}
rc.indexMap[value] = indexes
return true
}
}
func (rc *RandomizedCollection) Remove(value int) bool {
if indexes, exists := rc.indexMap[value]; exists {
var index int
for i := range indexes {
index = i
break
}
delete(indexes, index)
if len(indexes) < 1 {
delete(rc.indexMap, value)
}
newLen := len(rc.data) - 1
if index != newLen {
last := rc.data[newLen]
rc.data[index] = last
rc.data = rc.data[:newLen]
lastIndexes := rc.indexMap[last]
delete(lastIndexes, newLen)
lastIndexes[index] = struct{}{}
} else {
rc.data = rc.data[:newLen]
}
return true
} else {
return false
}
}
func (rc *RandomizedCollection) GetRandom() int {
randomIndex := rand.Intn(len(rc.data))
return rc.data[randomIndex]
}