【刷题日记】380. O(1) 时间插入、删除和获取随机元素
本次刷题日记的第 31 篇，力扣题为：380. O(1) 时间插入、删除和获取随机元素 ，中等
一、题目描述：
今天继续来刷 leetcode 每日一题，4 月份可不能再旷文（旷课）了，好习惯还是要继续保持，每天都要思考一下
二、这道题考察了什么思想？你的思路是什么？
咱今天来看的这道题，和其他的题又不一样了，今天是来实现一个类的基本成员方法，主要是对数组的增，删，查
看看本题给出我们重点的信息有哪些：
- 实现
RandomizedSet类 ，完成初始化，增加元素，删除元素，和查询随机元素 - 对于实现第一点，很容易就能想到，正常操作数组嘛，增加元素，就往数组后面追加，此处可以直接使用切片，需要删除元素，直接将尾巴的元素和要删除的这个元素换一下，然后缩小切片即可，查询随机元素那么就更简单了
- 题目还有一个要求，需要满足每个函数的 平均 时间复杂度为
O(1)，那么咱们的第二点就不满足这个要求了，因为咱们的第二点就使用一个切片是没有办法在 O(1) 的时间复杂度的情况上，完成对数组元素的删除的，因为咱们需要查询某个元素具体的位置才可以进行处理，此处是没有做到 O(1) 的 - 咱们可以好好思考片刻，切片加上哈希表是不是就可以实现，切片存储具体的元素，哈希表的 key 存放的也是具体元素，但是值是切片中的索引，那么这个时候，我们也就很容易处理了
例如咱们可以举一个例子：
根据上面这个例图，例如，我们需要查询数字 7 ，通过 helps[7] 我们就知道，7 这个数字是否存在，并且还可以得到这个数字在 nums 数组中的索引 是 2
迅速得到了上述信息之后，咱们做增，删，改，查 都是非常方便的 ， 那么接下来就一起来实现思路吧
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码，主要我们此处需要用到的是切片，也不是定长数组，此处的 hash 表，咱们可以使用 map 来进行实现
编码如下：
type RandomizedSet struct { nums []int helper map[int]int } func Constructor() RandomizedSet { return RandomizedSet{[]int{}, map[int]int{}} } func (this *RandomizedSet) Insert(val int) bool { // 判断这个值是否存在，可以查一下 hash 表 if _, ok := this.helper[val]; ok { return false } this.helper[val] = len(this.nums) this.nums = append(this.nums, val) return true } func (this *RandomizedSet) Remove(val int) bool { // 判断这个值是否存在，可以查一下 hash 表 index, ok := this.helper[val] if !ok { return false } // 去掉当前数组中的最后一个数 last := len(this.nums) - 1 this.nums[index] = this.nums[last] this.helper[this.nums[index]] = index this.nums = this.nums[:last] delete(this.helper, val) return true } func (this *RandomizedSet) GetRandom() int { // 获取一个随机索引，得到随机值 return this.nums[rand.Intn(len(this.nums))] }
根据上述的思路和具体实现的编码，我们就能很清晰的看到这个题的题解就很简单了
四、总结：
此处的时间复杂度不用多少，是 O(1) ，咱们就是为了这个目标而思考的，那么空间复杂就是 O(n) ，因为我们需要 O(n) 的空间来使用 哈希表 ， 用哈希表有没有觉得很简单呀
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
