LeetCode 380 常数时间插入、删除和获取随机元素 [Swift]
2019-09-24
题目
设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
1、insert(val)：当元素 val 不存在时，向集合中插入该项。
2、remove(val)：元素 val 存在时，从集合中移除该项。
3、getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :
// 初始化一个空的集合
RandomizedSet randomSet = new RandomizedSet();
// 向集合中插入 1 。返回 true 表示 1 被成功地插入
randomSet.insert(1);
// 返回 false ，表示集合中不存在 2
randomSet.remove(2);
// 向集合中插入 2 。返回 true 。集合现在包含 [1,2]
randomSet.insert(2);
// getRandom 应随机返回 1 或 2
randomSet.getRandom();
// 从集合中移除 1 ，返回 true 。集合现在包含 [2]
randomSet.remove(1);
// 2 已在集合中，所以返回 false
randomSet.insert(2);
// 由于 2 是集合中唯一的数字，getRandom 总是返回 2
randomSet.getRandom();
思路
首先，本题提出数据操作的 “平均时间复杂度为 O(1)”，对应常用数据结构的增删改查的复杂度，我们首先想到了 Hash Table / Set，利用 Hash Table 实现 insert 和 remove 的操作。
然后要求 getRandom 返回集合中的每一个元素 “概率相同”，由于 Hash Table 中的键值是有序的，我们可以先随机取得 Key 值，然后取得随机 Value 值。
附录代码如下:
class RandomizedSet {
var dataDict : [Int : Int]
/** Initialize your data structure here. */
init() {
dataDict = [Int : Int]()
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func insert(_ val: Int) -> Bool {
if dataDict[val] == nil {
dataDict[val] = val
return true
} else {
return false
}
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
func remove(_ val: Int) -> Bool {
let ret = dataDict.removeValue(forKey: val)
if ret == nil {
return false
}
return true
}
/** Get a random element from the set. */
func getRandom() -> Int {
let randomIndex = Int.random(in: 0...(dataDict.keys.count - 1))
let randomKey = ([Int](dataDict.keys))[randomIndex]
return dataDict[randomKey]!
}
}