算法练习16——O(1) 时间插入、删除和获取随机元素

算法练习16——O(1) 时间插入、删除和获取随机元素

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

实现RandomizedSet 类：
RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

哈希表+变长数组

哈希表实现插入和删除的O(1)，变长数组实现随机读取的O(1)

Python

class RandomizedSet:def __init__(self):self.nums = []self.indices = {}def insert(self, val: int) -> bool:if val in self.indices:return Falseself.indices[val] = len(self.nums)self.nums.append(val)return Truedef remove(self, val: int) -> bool:if val not in self.indices:return Falseid = self.indices[val]self.nums[id] = self.nums[-1]self.indices[self.nums[id]] = idself.nums.pop()del self.indices[val]return Truedef getRandom(self) -> int:return choice(self.nums)
# 作者：力扣官方题解
# 链接：/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Go

type RandomizedSet struct {nums    []intindices map[int]int
}func Constructor() RandomizedSet {return RandomizedSet{[]int{}, map[int]int{}}
}func (rs *RandomizedSet) Insert(val int) bool {if _, ok := rs.indices[val]; ok {return false}rs.indices[val] = len(rs.nums)rs.nums = append(rs.nums, val)return true
}func (rs *RandomizedSet) Remove(val int) bool {id, ok := rs.indices[val]if !ok {return false}last := len(rs.nums) - 1rs.nums[id] = rs.nums[last]rs.indices[rs.nums[id]] = idrs.nums = rs.nums[:last]delete(rs.indices, val)return true
}func (rs *RandomizedSet) GetRandom() int {return rs.nums[rand.Intn(len(rs.nums))]
}// 作者：力扣官方题解
// 链接：/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。