insert delete getrandom o1 dupli

leetcode地址

type RandomizedCollection struct {
    a []int
    m map[int]int
    r *rand.Rand
}

/** Initialize your data structure here. */
func Constructor() RandomizedCollection {
    return RandomizedCollection{
        a: []int{},
        m: make(map[int]int),
        r: rand.New(rand.NewSource(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 {
    this.a = append(this.a, val)
    if c, h := this.m[val]; h {
        this.m[val] = c + 1
        return false
    } else {
        this.m[val] = 1
    }
    return true
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
func (this *RandomizedCollection) Remove(val int) bool {
    if c, h := this.m[val]; h {
        if c == 1 {
            delete(this.m, val)
        } else {
            this.m[val] = c - 1
        }
        i := 0
        na := []int{}
        for i = range this.a {
            if this.a[i] == val {
                break
            }
            na = append(na, this.a[i])
        }
        this.a = append(na, this.a[i+1:]...)
        return true
    }
    return false
}

/** Get a random element from the collection. */
func (this *RandomizedCollection) GetRandom() int {
    r := this.r.Int() % len(this.a)
    return this.a[r]
}

Runtime: 152 ms, faster than 100.00% of Go online submissions for Insert Delete GetRandom O(1) - Duplicates allowed.