leetcode面试经典150题- 380. O(1) 时间插入、删除和获取随机元素

https://leetcode.cn/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150

go

type RandomizedSet struct {
    isHave map[int]int
    total  int
    arr    []int
}

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

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

func (this *RandomizedSet) Remove(val int) bool {
    if _, ok := this.isHave[val]; ok {
        // 把map对应下标换成交换后的
        this.isHave[this.arr[this.total-1]] = this.isHave[val]
        // 交换arr坐标里面的值
        this.arr[this.isHave[val]], this.arr[this.total-1] = this.arr[this.total-1], this.arr[this.isHave[val]]
        this.total--
        delete(this.isHave, val)
        return true
    }
    return false
}

func (this *RandomizedSet) GetRandom() int {
    return this.arr[rand.Intn(this.total)]
}

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