golang力扣leetcode 380.O(1)时间插入、删除和获取随机元素

380.O(1)时间插入、删除和获取随机元素 题解

题目要求每个操作都是O1的时间复杂度
思路：

1. 使用变长数组 + 哈希表
2. 删除是重点，介绍删除思路
3. 从map中获取val的下标index
4. 将变长数组的最后一个元素移动到下标index处，并将map中最后一个元素的下标更新为index
5. 在变长数组中删除最后一个元素，map中删除val

代码

type RandomizedSet struct {
	mp   map[int]int
	nums []int
}

func Constructor() RandomizedSet {
	return RandomizedSet{
		mp:   make(map[int]int),
		nums: make([]int, 0),
	}
}

func (this *RandomizedSet) Insert(val int) bool {
	//如果存在该对象则返回false
	if _, ok := this.mp[val]; ok {
		return false
	}
	//key:元素   val:这个元素在切片中的下标 存入map和切片中
	this.mp[val] = len(this.nums)
	this.nums = append(this.nums, val)
	return true
}

func (rs *RandomizedSet) Remove(val int) bool {
	//如果不存在返回false
	idx, ok := rs.mp[val]
	if !ok {
		return false
	}
	//last最后一个元素在下标
	last := len(rs.nums) - 1
	//将切片存val位置的元素修改成最后一个元素，即将需要删除的元素改为切片中最后一个元素
	rs.nums[idx] = rs.nums[last]
	//将map中原本在最后一个位置的元素的value，即在切片中的下标，修改成被删除元素的下标位置
	rs.mp[rs.nums[idx]] = idx
	//删除原来的最后一个元素
	rs.nums = rs.nums[:last]
	//在map中删除原来的元素
	delete(rs.mp, val)
	return true
}

func (this *RandomizedSet) GetRandom() int {
	return this.nums[rand.Intn(len(this.nums))]
}