type RandomizedSet struct {
data []int
idxMap map[int]int
}
func Constructor() RandomizedSet {
return RandomizedSet{
data:[]int{},
idxMap: map[int]int{},
}
}
func (this *RandomizedSet) Insert(val int) bool {
if _,ok:=this.idxMap[val];ok{
return false
}
// 记录元素插入的位置
this.idxMap[val]=len(this.data)
this.data = append(this.data,val)
return true
}
func (this *RandomizedSet) Remove(val int) bool {
id,ok:=this.idxMap[val]
if !ok{
return false
}
last:=len(this.data)-1
// 覆盖元素
this.data[id]=this.data[last]
// 修正最后一个元素的位置记录
this.idxMap[this.data[id]] = id
// 缩减切片
this.data=this.data[:last]
// 删除哈希表中的位置记录
delete(this.idxMap,val)
return true
}
func (this *RandomizedSet) GetRandom() int {
return this.data[rand.Intn(len(this.data))]
}
/**
* 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();
*/