380. Insert Delete GetRandom O(1)

题目

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present. remove(val): Removes an item val from the set if present. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

题意

构造一个结构体，并且该结构体有三个方法，插入删除和随机获取一个元素，要求时间复杂度都为O(1)。

例子

题解

使用map和数组作为结构体的属性。
插入一个先元素时，根据map中是否有对应key值，有的话返回false,没有的话则插入数组中，并将值作为key添加到map中，对应下标作为值。
删除时，从map中取出下标，与最后一个元素交换后，删除最后一个元素，同时更新map中的值。
有了数组就可以直接使用随机函数取得一个随机下标来获取一个随机元素

代码

type RandomizedSet struct {
    DataMap map[int]int
    Data []int
    LastIndex int
}


/** Initialize your data structure here. */
func Constructor() RandomizedSet {
    return RandomizedSet{
        DataMap : make(map[int]int),
        Data:make([]int,0),
        LastIndex:-1,
    }
}


/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
    if _,ok := this.DataMap[val];ok{
        return false
    }    
    this.LastIndex++
    this.Data = append(this.Data,val)
    this.DataMap[val] = this.LastIndex
    return true
}


/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
    if _,ok:=this.DataMap[val];!ok{
        return false
    }    
    
    index := this.DataMap[val]
    temp := this.Data[this.LastIndex]
    this.Data[this.LastIndex] = this.Data[index]
    this.Data[index]=temp
    
    this.DataMap[this.Data[index]] = index
    this.Data = this.Data[:this.LastIndex]
    delete(this.DataMap,val)
    this.LastIndex--
    return true
}


/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
    index:=rand.Intn(this.LastIndex+1)
    return this.Data[index]
}
 

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

总结

一开始直接使用map，没有用数组，直接 key和value都为元素值。而且go中遍历map是随机的。随意取随机值时直接for然后取第一个返回。能通过16个测试用例（一个18个），从结果来说确实是随机的。但是没通过可能是每个元素出现概率不等。

go中使用随机数
rand.Seek()设置随机种子 rand.Intn(n)获取0~n-1之间的随机数。除了int还有很多其他类型的
需要注意在需要一次性获取多个随机值时，rand.Seek()只需要调用一次，如果在for中每一次获取都seek一次，那么会获取到相同的随机值。