简介：

Leetcode 题目 380: “插入、删除、获取随机元素 O(1)”(https://leetcode.com/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150) 要求实现一个能在常数时间内完成插入、删除和随机访问操作的数据结构。本文将讨论这个问题在 Go (Golang) 中的三种不同实现版本。接下来，我将比较这些变体，并解释各自的优缺点。

实现 RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 类。

bool insert(int val) 如果 val 不在集合中，则插入 val。如果不存在则返回 true，否则返回 false。

bool remove(int val) 如果 val 存在于集合中，则移除 val。如果存在则返回 true，否则返回 false。

int getRandom() 调用此方法时保证至少有一个元素，返回当前集合中的一个随机元素。每个元素必须以相同的概率被返回。

您必须实现这些类函数，使得每个函数的平均时间复杂度为 O(1)。

    type RandomizedSet struct {  
        rand map[int]struct{}  
    }  

    func Constructor() RandomizedSet {  
        return RandomizedSet{  
            rand: make(map[int]struct{}),  
        }  
    }  

    // 插入一个值到集合中，如果插入成功返回true，否则返回false
    func (this *RandomizedSet) Insert(val int) bool {  
        存在 := false  
        if _, ok := this.rand[val]; !ok {  
            存在 = true  
            this.rand[val] = struct{}{}  
        }  
        return 存在  
    }  

    // 从集合中移除一个值，如果移除成功返回true，否则返回false
    func (this *RandomizedSet) Remove(val int) bool {  
        存在 := false  
        if _, ok := this.rand[val]; ok {  
            存在 = true  
            delete(this.rand, val)  
        }  
        return 存在  
    }  

    // 从集合中随机返回一个值
    func (this *RandomizedSet) GetRandom() int {  
        集合长度 := len(this.rand)  
        随机数 := rand.Intn(集合长度)  
        i := 0  
        for k := range this.rand {  
            if i == 随机数 {  
                return k  
            }  
            i++  
        }  
        return -1  
    }

好处：

• 简单的实现方式。
• 使用内置映射来存储元素。

不足：

• 获取随机元素需要线性时间，因为必须遍历映射中的所有元素。
• 内存使用效率不高，因为它只利用了映射中的键。

    type 随机数集版本二 struct { 
        随机数生成器 *rand.Rand 
        数组    []int 
        索引     map[int]int 
    } 

    func 构造函数版本二() 随机数集版本二 { 
        return 随机数集版本二{ 
            随机数生成器: rand.New(rand.NewSource(time.Now().UnixNano())), 
            数组:    []int{}, 
            索引: make(map[int]int), 
        } 
    } 

    func (this *随机数集版本二) 插入版本二(val int) bool { 
        // 检查值是否存在索引中
        if _, 存在 := this.索引[val]; 存在 { 
            return false 
        } 
        this.索引[val] = len(this.数组) 
        // 将val追加到数组列表的末尾
        this.数组 = append(this.数组, val) 
        return true 
    } 

    func (this *随机数集版本二) 删除版本二(val int) bool { 
        index, 存在 := this.索引[val] 
        if !存在 { 
            return false 
        } 
        lastElement := this.数组[len(this.数组)-1] 
        this.数组[index] = lastElement 
        this.索引[lastElement] = index 
        // 从数组中移除最后一个元素
        this.数组 = this.数组[:len(this.数组)-1] 
        // 从索引中移除指定的键值
        delete(this.索引, val) 
        return true 
    } 

    func (this *随机数集版本二) 获取随机数版本二() int { 
        // 生成一个在0到长度-1之间的随机整数
        return this.数组[this.随机数生成器.Intn(len(this.数组))] 
    }

优点如下：

• 插入和删除操作所需时间是常量的。
• 获取随机元素所需时间是常量的。

缺点如下：

• 实现更为复杂，因为用了两种数据结构：映射和数组。
• 虽然内存使用更高效，但仍需复制一些数据。

    type RandomizedSetVer3 struct {  
        randGen *rand.Rand  // 随机生成器  
        nums    []int       // 存储的数字列表  
        indices map[int]int // 数字到索引的映射  
        length  int         // 当前列表长度  
    }  

    func ConstructorVer3() RandomizedSetVer3 {  
        return RandomizedSetVer3{  
            randGen: rand.New(rand.NewSource(time.Now().UnixNano())),  // 初始化随机生成器  
            nums:    []int{},  
            indices: make(map[int]int),  
            length:  0,  
        }  
    }  

    func (this *RandomizedSetVer3) InsertVer3(val int) bool {  
        if _, exists := this.indices[val]; exists {  
            return false  // 插入值：如果值已存在，返回false；否则插入值，返回true  
        }  
        this.indices[val] = this.length  
        this.nums = append(this.nums, val)  
        this.length++  
        return true  
    }  

    func (this *RandomizedSetVer3) RemoveVer3(val int) bool {  
        index, exists := this.indices[val]  
        if !exists {  
            return false  // 移除值：如果值存在，将其移除并返回true；如果值不存在，返回false  
        }  
        lastElement := this.nums[this.length-1]  
        this.nums[index] = lastElement  
        this.indices[lastElement] = index  
        this.nums = this.nums[:this.length-1]  
        this.length--  
        delete(this.indices, val)  
        return true  
    }  

    func (this *RandomizedSetVer3) GetRandomVer3() int {  
        return this.nums[this.randGen.Intn(this.length)]  // 随机获取值：从结构体中随机返回一个值  
    }

好处:

• 插入、删除和检索任意元素都只需要常数时间。
• 从而通过减少数据冗余来优化内存使用。

这里有一些不足：

相比第一种方案，实现起来要更复杂一些。

第一个变体实现起来很简单，但在随机访问元素方面效率较差。第二个变体通过同时使用数组和映射来提高性能，但这也使得代码更加复杂。第三个变体优化了内存使用，并且保持所有操作的时间复杂度为常数，因此它是这里提出的解决方案中最好的。然而，基准测试表明，它的性能与第二个变体相当。

像往常一样，欢迎各位留言评论。可以在GitHub找到代码。

感谢您一直读到最后。在您离开之前，想提醒您：

• 请为作者的 点赞 和 关注 表示支持！
• 关注我们 X（即Twitter） | 领英 | YouTube | Discord
• 浏览我们的其他平台：In Plain English | CoFeed | Differ
• 更多内容请浏览 Stackademic.com