2021-11-10：O(1) 时间插入、删除和获取随机元素。实现RandomizedSet 类：RandomizedSet()

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    rand.Seed(time.Now().Unix())
    nrs := NewRandomizedSet()
    nrs.insert(6)
    nrs.insert(3)
    nrs.insert(7)
    nrs.insert(9)
    nrs.insert(8)
    fmt.Println(nrs.getRandom())
}

type RandomizedSet struct {
    keyIndexMap map[int]int
    indexKeyMap map[int]int
    size        int
}

func NewRandomizedSet() *RandomizedSet {
    res := &RandomizedSet{}
    res.keyIndexMap = make(map[int]int)
    res.indexKeyMap = make(map[int]int)
    res.size = 0
    return res
}

func (this *RandomizedSet) insert(val int) bool {
    if _, ok := this.keyIndexMap[val]; !ok {
        this.keyIndexMap[val] = this.size
        this.indexKeyMap[this.size] = val
        this.size++
        return true
    }
    return false
}

func (this *RandomizedSet) remove(val int) bool {
    if _, ok := this.keyIndexMap[val]; ok {
        deleteIndex := this.keyIndexMap[val]
        this.size--
        lastIndex := this.size
        lastKey := this.indexKeyMap[lastIndex]
        this.keyIndexMap[lastKey] = deleteIndex
        this.indexKeyMap[deleteIndex] = lastKey
        delete(this.keyIndexMap, val)
        delete(this.indexKeyMap, lastIndex)
        return true
    }
    return false
}

func (this *RandomizedSet) getRandom() int {
    if this.size == 0 {
        return -1
    }
    randomIndex := rand.Intn(this.size)
    return this.indexKeyMap[randomIndex]
}