Design - 381. Insert Delete GetRandom O(1) - Duplicates allowed

381. Insert Delete GetRandom O(1) - Duplicates allowed

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

Note: Duplicate elements are allowed.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

思路：

这一题是380题的变形题，条件多了元素可以重复。做法还是map加上数组，这次map的key依然是数值val，但是map的value就是一个数组，存储的是val在数值数组arr中的索引，同时数值数值arr存贮的不再只是数值，而是还有在map的索引数组中的下标，这样当把数组最后一个元素移动到目标元素的位置的时候，才能根据这个字段去更新map的索引数组。

代码：

go：

type RandomizedCollection struct {
    m map[int][]int
    arr []*node
}

type node struct {
    val int 
    index int // map value中的index
}

/** Initialize your data structure here. */
func Constructor() RandomizedCollection {
    return RandomizedCollection {
        m: make(map[int][]int), 
        arr:make([]*node, 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 {
    indexs, ok := this.m[val]
    if !ok {
        n := &node{val:val, index:0}
        this.m[val] = []int{len(this.arr)}
        this.arr = append(this.arr, n)
        return true
    } else {
        n := &node{val:val, index:len(indexs)}
        this.m[val] = append(indexs, len(this.arr))
        this.arr = append(this.arr, n)
        return false
    }
    return true    
}


/** Removes a value from the collection. Returns true if the collection contained the specified element. */
func (this *RandomizedCollection) Remove(val int) bool {
    targetIndexs, ok := this.m[val]
    if !ok || len(targetIndexs) == 0 {
        return false
    }
    
    // 1. 取出targetIndexs最后一个索引，根据这个索引找到要删除的元素在数组中的位置
    tIndex := targetIndexs[len(targetIndexs)-1]
    
    // 2. 取出数组中的最后一个元素
    lastNode := this.arr[len(this.arr)-1]
    
    // 3. 把最后一个元素交换到tIndex上,然后删除arr最后一个元素
    this.arr[tIndex] = lastNode
    this.arr = this.arr[:len(this.arr)-1]
    
    // 4. 更新lastNode在map的value数组中的位置
    lastIndexs, _ := this.m[lastNode.val]
    lastIndexs[lastNode.index] = tIndex
    
    // 5. 删除目标元素在map的value数组中的最后一位
    targetIndexs = targetIndexs[:len(targetIndexs)-1]
    this.m[val] = targetIndexs
    
    return true
}


/** Get a random element from the collection. */
func (this *RandomizedCollection) GetRandom() int {
    r := rand.Int31n(int32(len(this.arr)))
    return this.arr[int(r)].val
}


/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */