该题目要求设计一个支持 O(1) 时间复杂度的数据结构，实现插入、删除和随机获取元素的功能。核心方案是结合数组和哈希表：数组用于存储元素以支持 O(1) 随机访问，哈希表用于存储元素到索引的映射以支持 O(1) 查找。删除操作通过将待删元素与数组末尾元素交换位置来实现 O(1) 复杂度。该结构适用于抽奖系统、随机推荐、游戏事件触发及负载均衡等场景。
题目要求实现 类，支持以下操作：
RandomizedSetRandomizedSet()：初始化对象。bool insert(int val)：当元素 val 不存在时插入，返回 true；否则返回 false。bool remove(int val)：当元素 val 存在时移除，返回 true；否则返回 false。int getRandom()：随机返回集合中的一项，每个元素被返回的概率相同。所有函数必须满足平均时间复杂度为 O(1)。
示例：
输入 ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []]
输出 [null, true, false, true, 2, true, false, 2]
解释 RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1。返回 true。
randomizedSet.remove(2); // 返回 false，表示集合中不存在 2。
randomizedSet.insert(2); // 向集合中插入 2。返回 true。集合现在包含 [1,2]。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2。
randomizedSet.remove(1); // 从集合中移除 1，返回 true。集合现在包含 [2]。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2。
提示：
-2^31 <= val <= 2^31 - 1insert、remove 和 getRandom 函数 2 * 10^5 次getRandom 方法时，数据结构中至少存在一个元素核心思路是使用数组和字典：数组用来存储元素，支持 O(1) 的随机访问；字典用来存储元素到索引的映射，支持 O(1) 的查找和删除。删除时，将最后一个元素移到被删除元素的位置，然后删除最后一个元素，保证 O(1) 的删除操作。
下面是完整的 Swift 解决方案：
class RandomizedSet {
// 数组：存储所有元素，支持 O(1) 随机访问
private var array: [Int]
// 字典：存储元素到索引的映射，支持 O(1) 查找和删除
private var dict: [Int: Int]
init() {
self.array = []
self.dict = [:]
}
/// 插入元素
func insert(_ val: Int) -> Bool {
// 如果元素已存在，返回 false
if dict[val] != nil {
return false
}
// 将元素添加到数组末尾
array.append(val)
// 记录元素在数组中的索引
dict[val] = array.count - 1
return true
}
/// 删除元素
func remove(_ val: Int) -> Bool {
// 如果元素不存在，返回 false
guard let index = dict[val] else {
return false
}
// 获取数组最后一个元素
let lastElement = array[array.count - 1]
// 将最后一个元素移到被删除元素的位置
array[index] = lastElement
// 更新最后一个元素的索引映射
dict[lastElement] = index
// 删除数组最后一个元素（O(1) 操作）
array.removeLast()
// 删除字典中的映射
dict.removeValue(forKey: val)
return true
}
/// 随机获取元素
func getRandom() -> Int {
// 随机选择一个索引
let randomIndex = Int.random(in: 0..<array.count)
return array[randomIndex]
}
}
我们使用了两个数据结构：
array：一个数组，用来存储所有元素。数组支持 O(1) 的随机访问，这对于 getRandom() 操作非常重要。dict：一个字典，用来存储元素到索引的映射。字典支持 O(1) 的查找和删除，这对于 insert() 和 remove() 操作非常重要。insert() 是 O(1)，但 remove() 是 O(n)（需要查找并移动元素），getRandom() 是 O(1)。insert() 和 remove() 平均 O(1)，但 getRandom() 是 O(n)（不支持随机访问）。false。true：插入成功。时间复杂度是 O(1)。
这是最关键的删除操作，需要巧妙地处理：
false。Int.random(in: 0..<array.count)。时间复杂度是 O(1)。
lastElement 就是被删除的元素本身。不是直接删除数组中间的元素，而是将最后一个元素移到被删除元素的位置，然后删除最后一个元素。避免了移动数组中间的元素（O(n) 操作）。
let randomizedSet = RandomizedSet()
print("insert(1): \(randomizedSet.insert(1))") // true
print("insert(2): \(randomizedSet.insert(2))") // true
print("insert(3): \(randomizedSet.insert(3))") // true
print("getRandom(): \(randomizedSet.getRandom())") // 随机返回 1、2 或 3
print("remove(2): \(randomizedSet.remove(2))") // true
print("remove(2): \(randomizedSet.remove(2))") // false（已删除）
print("getRandom(): \(randomizedSet.getRandom())") // 随机返回 1 或 3
let randomizedSet = RandomizedSet()
print("insert(1): \(randomizedSet.insert(1))") // true
print("remove(2): \(randomizedSet.remove(2))") // false
print("insert(2): \(randomizedSet.insert(2))") // true
print("getRandom(): \(randomizedSet.getRandom())") // 1 或 2
print("remove(1): \(randomizedSet.remove(1))") // true
print("insert(2): \(randomizedSet.insert(2))") // false
print("getRandom(): \(randomizedSet.getRandom())") // 2
let randomizedSet = RandomizedSet()
// 插入 1000 个元素
for i in 0..<1000 {
_ = randomizedSet.insert(i)
}
print("插入 1000 个元素后，getRandom(): \(randomizedSet.getRandom())")
// 删除前 500 个元素
for i in 0..<500 {
_ = randomizedSet.remove(i)
}
print("删除 500 个元素后，getRandom(): \(randomizedSet.getRandom())")
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
init() | O(1) | 初始化空数组和字典 |
insert(_ val: Int) | O(1) 平均 | 数组 append() 是 O(1)，字典插入平均 O(1) |
remove(_ val: Int) | O(1) 平均 | 字典查找平均 O(1)，数组操作是 O(1) |
getRandom() | O(1) | 数组随机访问是 O(1) |
所有操作的平均时间复杂度都是 O(1)。
array：存储所有元素，最多存储 n 个元素，O(n)dict：存储元素到索引的映射，最多存储 n 个键值对，O(n)总空间复杂度：O(n)
这种数据结构设计在实际开发中应用非常广泛：
需要从参与者中随机选择一个获奖者，需快速添加和移除参与者。
从候选列表中随机推荐内容，需动态添加和移除候选内容。
从事件池中随机触发事件，需动态注册和注销事件。
从服务器列表中随机选择一个服务器，需动态添加和移除服务器。
这道题涉及重要的设计思想：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online