2021-11-10:o (1) time inserts, deletes and obtains random elements. Implement ra

2021-11-10：O(1) Time insertion 、 Delete and get random elements . Realization RandomizedSet class ：RandomizedSet() initialization RandomizedSet object .bool insert(int val) When element val When there is no , Insert the item into the collection , And back to true ; otherwise , return false .bool remove(int val) When element val In existence , Remove the item from the collection , And back to true ; otherwise , return false .int getRandom() Random return of an item in an existing collection （ The test case guarantees that there is at least one element in the collection when this method is called ）. Every element should have Same probability Returned . You must implement all the functions of the class , And satisfy the of each function Average The time complexity is O(1) . Power button 380.

answer 2021-11-10：

Two hash tables .

v→index.

index→v.

index It must be continuous .

Delete the element in the middle , Replace... With the last element . such index It's continuous .

The code to use golang To write . The code is as follows ：

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]
}

The results are as follows ：

picture

---

Zuo Shen java Code