O(1) 时间插入、删除和获取随机元素

O(1) 时间插入、删除和获取随机元素

https://leetcode.cn/problems/insert-delete-getrandom-o1/description/

type RandomizedSet struct {
    arr       []int
    randomMap map[int]int
}

func Constructor() RandomizedSet {
    return RandomizedSet{
        arr:       []int{},
        randomMap: make(map[int]int),
    }
}

func (this *RandomizedSet) Insert(val int) bool {
    if _, ok := this.randomMap[val]; ok {
        return false
    }
    this.arr = append(this.arr, val)
    this.randomMap[val] = len(this.arr) - 1
    return true
}

func (this *RandomizedSet) Remove(val int) bool {
    index, ok := this.randomMap[val]
    if !ok {
        return false
    }
    valToSwap := this.arr[len(this.arr)-1]
    this.arr[index], this.arr[len(this.arr)-1] = this.arr[len(this.arr)-1], this.arr[index]
    this.randomMap[valToSwap] = index
    this.arr = this.arr[:len(this.arr)-1]
    delete(this.randomMap, val)
    return true
}

func (this *RandomizedSet) GetRandom() int {
    if len(this.arr) == 0 {
        return -1 // 或者抛出错误
    }
    return this.arr[rand.Intn(len(this.arr))]
}

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