O(1)时间插入、删除和获取随机元素（补充解释）

2025年8月6日 · 阅读需 16 分钟

Eureka X

Mr.Nobody

力扣面试经典——380题

📘 关于此题示例解释

📥 输入格式说明

输入分为两行：

第一行：["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
- 这是要执行的操作序列
第二行：[[], [1], [2], [2], [], [1], [2], []]
- 这是每个操作对应的参数

🔄 逐步执行过程

让我按照时间顺序来解释每一步发生了什么：

1️⃣ 创建对象

操作: "RandomizedSet"
参数: []
✨ 创建一个新的 RandomizedSet 对象，初始为空
💾 内存状态：数组为空，哈希表为空

2️⃣ 插入元素 1

操作: "insert"
参数: [1]
执行: randomizedSet.insert(1)
🔍 检查哈希表，发现 1 不存在
➕ 将 1 添加到数组位置 0
📝 在哈希表中记录：1 → 索引 0
✅ 返回 true（插入成功）
📊 当前状态：数组 [1]，哈希表 {1: 0}

3️⃣ 删除元素 2

操作: "remove"
参数: [2]
执行: randomizedSet.remove(2)
🔍 检查哈希表，发现 2 不存在
❌ 无法删除不存在的元素
❌ 返回 false（删除失败）
🔁 状态不变：数组 [1]，哈希表 {1: 0}

4️⃣ 插入元素 2

操作: "insert"
参数: [2]
执行: randomizedSet.insert(2)
🔍 检查哈希表，发现 2 不存在
➕ 将 2 添加到数组位置 1
📝 在哈希表中记录：2 → 索引 1
✅ 返回 true（插入成功）
📊 当前状态：数组 [1, 2]，哈希表 {1: 0, 2: 1}

5️⃣ 随机获取元素

操作: "getRandom"
参数: []
执行: randomizedSet.getRandom()
🎲 数组中有两个元素 [1, 2]
🎯 随机返回其中一个元素（可能是 1 或 2）
📋 示例中显示返回了 2
🔁 状态不变：数组 [1, 2]，哈希表 {1: 0, 2: 1}

6️⃣ 删除元素 1

操作: "remove"
参数: [1]
执行: randomizedSet.remove(1)
🔍 检查哈希表，发现 1 存在，索引为 0
🔚 获取数组最后一个元素：2
↔️ 将元素 2 移动到索引 0（覆盖元素 1）
🔄 更新哈希表中 2 的索引为 0
🗑️ 从哈希表中删除元素 1 的记录
✅ 返回 true（删除成功）
📊 当前状态：数组 [2]，哈希表 {2: 0}

7️⃣ 插入元素 2

操作: "insert"
参数: [2]
执行: randomizedSet.insert(2)
🔍 检查哈希表，发现 2 已经存在
⛔ 不允许重复插入
❌ 返回 false（插入失败）
🔁 状态不变：数组 [2]，哈希表 {2: 0}

8️⃣ 随机获取元素

操作: "getRandom"
参数: []
执行: randomizedSet.getRandom()
🎯 数组中只有一个元素 [2]
🎲 只能返回元素 2
✅ 返回 2
🔁 状态不变：数组 [2]，哈希表 {2: 0}

📤 最终输出结果

[null, true, false, true, 2, true, false, 2]

对应每个操作的返回值：

null - 创建对象不返回值
true - 成功插入 1
false - 删除不存在的 2 失败
true - 成功插入 2
2 - 随机返回 2（可能是 1 或 2）
true - 成功删除 1
false - 插入已存在的 2 失败
2 - 随机返回 2（唯一元素）

💡 关键理解点

🧮 集合特性：不允许重复元素
🎲 随机性：getRandom 操作是随机的，但在示例中为了演示方便，给出了具体结果
⚡ 高效操作：所有操作都是 O(1) 时间复杂度
🔧 内部机制：通过数组+哈希表的组合实现高效操作

⚠️ 代码语法说明

该题目示例解释中的这句代码：

RandomizedSet randomizedSet = new RandomizedSet();

这其实是一句伪代码，真正的C代码应该是：

RandomizedSet* randomizedSet = randomizedSetCreate();

因为在我们之前的代码中：

randomizedSetCreate() 函数负责分配内存和初始化对象
它返回一个指向 RandomizedSet 的指针

这句也是伪代码：

randomizedSet.insert(1);

真正的C代码应该是：

randomizedSetInsert(randomizedSet, 1);

哈希表与UT_hash_handle

🤔 为什么需要哈希表？

因为数组可以快速通过索引访问元素，但无法快速查找某个值是否存在于数组中。比如我们要删除值为 5 的元素，我们需要先找到它在数组中的位置，这就需要遍历整个数组，时间复杂度是 O(n)。

⚡ 哈希表的作用就是解决这个问题：快速查找元素在数组中的位置。

🔧 关于 UT_hash_handle

当你定义了包含 UT_hash_handle 的结构体后，就可以使用这些宏：

// 🔍 查找元素
HASH_FIND_INT(obj->indices, &val, tmp);

// ➕ 添加元素
HASH_ADD_INT(obj->indices, value, tmp);

// 🗑️ 删除元素
HASH_DEL(obj->indices, tmp);

// 🔁 遍历哈希表
HASH_ITER(hh, obj->indices, curr, tmp)

这些宏内部会通过 hh 字段来操作哈希表的内部结构。

❓ 为什么必须包含这个字段？

typedef struct {
    int value;
    int index;
    UT_hash_handle hh;  // ⚠️ 必须包含这个字段
} HashItem;

✅ uthash 宏的要求：所有使用 uthash 的结构体都必须包含一个 UT_hash_handle 类型的字段

🔗 内部管理需要：没有这个字段，uthash 就无法维护哈希表的内部链接关系

🏷️ 命名可以自定义：字段名不一定要是 hh，可以是任何名字，比如 hash_handle

📝 总结

UT_hash_handle hh 是：

🔹 一个由 uthash 库定义的结构体字段

🔗 用于维护哈希表内部的链接关系

🔑 是使用 uthash 宏操作哈希表的必要条件

🔄 类似于链表节点中的 next 指针，但功能更复杂

randomizedSetCreate 函数详解

这个函数是 RandomizedSet 数据结构的构造函数，用于创建和初始化一个新的 RandomizedSet 对象。

函数逐行解析randomizedSetCreate

RandomizedSet* randomizedSetCreate() {
    srand(time(NULL)); // 初始化随机数种子
    RandomizedSet* obj = (RandomizedSet*)malloc(sizeof(RandomizedSet));
    obj->nums = (int*)malloc(sizeof(int) * 200000); // 预分配足够空间
    obj->numsSize = 0;                              // 初始元素个数为0
    obj->indices = NULL;                            // 哈希表初始为空
    return obj;
}

1. srand(time(NULL)); - 初始化随机数种子

srand() 是C标准库函数，用于设置随机数生成器的种子
time(NULL) 返回当前时间戳作为种子
这样可以确保每次程序运行时生成的随机数序列都不同
为后续的 randomizedSetGetRandom() 函数做准备

2. RandomizedSet* obj = (RandomizedSet*)malloc(sizeof(RandomizedSet)); - 分配主对象内存

malloc() 分配内存
sizeof(RandomizedSet) 计算 RandomizedSet 结构体所需字节数
强制类型转换为 RandomizedSet* 指针类型
这里创建了主对象，但其中的成员还未初始化

3. obj->nums = (int*)malloc(sizeof(int) * 200000); - 分配数组内存

为存储实际元素的数组 nums 分配内存
预分配 200000 个 int 的空间（题目限制最大调用次数）
这样避免了动态扩容的开销，提高性能

4. obj->numsSize = 0; - 初始化元素计数

设置数组当前元素个数为 0
表示刚开始时集合为空

5. obj->indices = NULL; - 初始化哈希表

将哈希表指针设置为 NULL
在 uthash 库中，NULL 表示空的哈希表
这是 uthash 库要求的初始化方式

6. return obj; - 返回创建的对象

返回指向新创建对象的指针
调用者可以通过这个指针使用对象的各种方法

内存布局示意图

创建完成后，内存结构如下：

RandomizedSet 对象:
+------------+
| nums       | ---> [int 数组，大小为200000，初始为空]
+------------+
| numsSize   | = 0
+------------+
| indices    | = NULL (空哈希表)
+------------+

重要设计考虑

预分配数组空间：避免动态扩容，提高性能
随机数种子初始化：确保随机性
正确的初始化：所有成员都被正确初始化
内存管理：为后续的插入、删除操作做好准备

使用示例

// 调用这个函数创建对象
RandomizedSet* mySet = randomizedSetCreate();

// 现在可以使用 mySet 进行各种操作
// randomizedSetInsert(mySet, 1);
// randomizedSetRemove(mySet, 1);
// randomizedSetGetRandom(mySet);

randomizedSetInsert 函数详解

函数逐步解析 randomizedSetInsert

这个函数用于向 RandomizedSet 集合中插入一个新元素，确保集合中没有重复元素。

函数签名解析

bool randomizedSetInsert(RandomizedSet* obj, int val)

返回类型: bool - 插入成功返回 true，失败返回 false
参数1: RandomizedSet* obj - 指向要操作的 RandomizedSet 对象
参数2: int val - 要插入的元素值

bool randomizedSetInsert(RandomizedSet* obj, int val) {
    HashItem* tmp = NULL;
    // 在哈希表中查找元素是否已存在
    HASH_FIND_INT(obj->indices, &val, tmp);
    if (tmp != NULL) {
        return false; // 元素已存在，插入失败
    }
    
    // 将新元素添加到数组末尾
    obj->nums[obj->numsSize] = val;
    
    // 在哈希表中创建新节点，记录元素值和其在数组中的索引
    tmp = (HashItem*)malloc(sizeof(HashItem));
    tmp->value = val;
    tmp->index = obj->numsSize;
    HASH_ADD_INT(obj->indices, value, tmp);
    
    obj->numsSize++; // 数组元素个数增加
    return true;
}

步骤1：检查元素是否已存在

HashItem* tmp = NULL;
// 在哈希表中查找元素是否已存在
HASH_FIND_INT(obj->indices, &val, tmp);
if (tmp != NULL) {
    return false; // 元素已存在，插入失败
}

初始化一个临时指针 tmp 为 NULL
使用 HASH_FIND_INT 宏在哈希表中查找值为 val 的元素
如果找到了（tmp != NULL），说明元素已存在，直接返回 false

步骤2：插入新元素到数组

obj->nums[obj->numsSize] = val;

将新元素 val 添加到数组 nums 的索引 numsSize 处

步骤3：更新哈希表映射关系

tmp = (HashItem*)malloc(sizeof(HashItem));
tmp->value = val;
tmp->index = obj->numsSize;
HASH_ADD_INT(obj->indices, value, tmp);

为新元素分配哈希表节点内存 HashItem
设置节点的值 value 为插入的元素值
设置节点的索引 index 为该元素在数组中的位置
使用 HASH_ADD_INT 宏将新节点添加到哈希表中

步骤4：更新 numsSize 大小

obj->numsSize++;
return true;

将数组元素计数器 numsSize 增加1
返回 true 表示插入成功

数据结构设计特点

基于UTHash库：

使用 HASH_FIND_INT 和 HASH_ADD_INT 实现哈希表操作
哈希表存储 HashItem 结构体，维护元素值到数组索引的映射

数组+哈希表组合：

数组 nums 存储实际元素值
哈希表 indices 维护元素值到索引的映射关系

时间复杂度：

插入操作时间复杂度为O(1)

关键数据结构

HashItem：包含 value（元素值）和 index（在数组中的索引）
nums 数组：存储所有插入的元素
numsSize：记录当前数组中元素的数量

randomizedSetRemove 函数详解

举例解释randomizedSetRemove

假设我们有一个 RandomizedSet，其初始状态如下：

obj->nums = [10, 20, 30, 40] (数组)
obj->numsSize = 4
obj->indices 哈希表内容：
- key=10, index=0
- key=20, index=1
- key=30, index=2
- key=40, index=3

现在我们要删除元素 20。

初始状态 数组: [10, 20, 30, 40] 哈希表:

10 -> index=0
20 -> index=1
30 -> index=2
40 -> index=3

步骤 1: 查找要删除的元素

HashItem* tmp = NULL;
HASH_FIND_INT(obj->indices, &val, tmp);

在哈希表中查找 val=20:

找到元素 20，其索引为 index=1
tmp 指向元素 20 的哈希项

步骤 2: 获取索引和最后一个元素

int index = tmp->index;// index = 1
int lastValue = obj->nums[obj->numsSize - 1]; // lastValue = 40

index = 1 (要删除元素 20 的位置)
lastValue = 40 (数组最后一个元素)

步骤 3: 用最后一个元素覆盖待删除元素

obj->nums[index] = lastValue;

执行后数组变为: [10, 40, 30, 40]

将最后一个元素 40 放在索引 1 的位置，覆盖了原来的 20

步骤 4: 更新最后一个元素在哈希表中的索引

HashItem* lastItem = NULL;
HASH_FIND_INT(obj->indices, &lastValue, lastItem);
if (lastItem != NULL) { lastItem->index = index; }

查找元素 40 在哈希表中的记录
将其索引从 3 更新为 1 (因为现在它在数组的索引 1 位置)

更新后哈希表:

10 -> index=0
20 -> index=1 (即将被删除)
30 -> index=2
40 -> index=1

步骤 5: 从哈希表中删除目标元素并释放内存

HASH_DEL(obj->indices, tmp);
free(tmp);

从哈希表中删除元素 20 的记录
释放该哈希项的内存

删除后哈希表:

10 -> index=0
30 -> index=2
40 -> index=1

步骤 6: 减少数组大小计数

obj->numsSize--;

numsSize 从 4 减少到 3

最终状态 数组: [10, 40, 30] (逻辑上最后一个40被忽略) 哈希表:

10 -> index=0
30 -> index=2
40 -> index=1 numsSize: 3

成功删除元素 20，返回 true。

为什么用最后一个元素覆盖？

核心原因：效率优化

1. 直接访问 vs 遍历访问

最后一个元素：obj->nums[obj->numsSize - 1] - O(1) 直接访问
其他元素：需要遍历或计算索引 - 增加复杂度

2. 避免批量元素移动 使用最后一个元素覆盖只需一次操作，而用其他元素需要移动多个元素：

示例：删除元素 20（索引1） 数组 [10, 20, 30, 40, 50]

使用最后一个元素（推荐）：

用 50 覆盖 20：[10, 50, 30, 40, 50]
一次操作，O(1) 复杂度

使用下一个元素（不推荐）：

需要 30→20, 40→30, 50→40：[10, 30, 40, 50, 50]
三次移动，O(n) 复杂度

关键优势

保持 O(1) 时间复杂度 这是 RandomizedSet 数据结构的核心设计目标

实现简单

无需循环
代码简洁不易出错

维护随机访问特性 不影响剩余元素的等概率随机访问

总结使用最后一个元素覆盖是一种经典优化技巧，确保删除操作在常数时间内完成，同时保持数据结构的完整性和随机访问特性。

randomizedSetFree 函数详解

函数目的

释放整个 RandomizedSet 对象及其包含的所有资源，避免内存泄漏。

逐步执行流程

1. 释放哈希表中所有节点

HashItem* curr, *tmp;
HASH_ITER(hh, obj->indices, curr, tmp) { HASH_DEL(obj->indices, curr); free(curr); }

执行过程：

使用 HASH_ITER 安全地遍历哈希表中的每个节点
curr 指向当前节点，tmp 用于保存下一个节点的指针（防止遍历过程中断）
对每个节点：
- HASH_DEL(obj->indices, curr) 从哈希表中删除节点
- free(curr) 释放节点内存

为什么需要 tmp？ 在遍历过程中直接 free(curr) 会破坏哈希表结构，导致无法继续遍历，所以需要提前保存下一个节点的指针。

2. 释放数组内存

free(obj->nums);

释放存储元素的动态数组内存

3. 释放对象本身

free(obj);

释放 RandomizedSet 结构体本身的内存

内存管理要点

释放顺序很重要

先释放哈希表节点（HashItem）
再释放数组
最后释放对象本身

避免内存泄漏

确保每个 malloc 都有对应的 free
哈希表中的每个节点都需要单独释放
对象包含的所有动态分配内存都需要释放

使用示例

当不再需要 RandomizedSet 对象时调用：

RandomizedSet* set = randomizedSetCreate(); // ... 使用 set 进行各种操作 
randomizedSetFree(set); // 释放所有资源

这样确保程序不会出现内存泄漏问题。

randomizedSetGetRandom 就是随机获取一个索引然后返回，就不再详细解释了。

这是目前我做题以来遇到的最困难的一道题，题目看不懂、示例看不懂、AI给出题目代码，还是看不懂！😂😂😂

现在嘛，勉强理解啦~🥱

我现在不像是在解题，更像是在学习，普通的力扣题目，我有点思路，但代码往往又臭又长，甚至连逻辑都是错乱的都没发现！😑

于是通常是叫AI给出最优解，然后尝试去理解它，为了避免看了就忘，于是我还是在AI的辅助下，写下像以上这些题解总结。我也在怀疑这种学习方法真的 有效吗？真能提升我的编程水平吗？我该不会是在做无用功吧？

统义灵码：你的学习方法其实是有一定效果的，但可以进一步优化。下面是对你当前学习方式的分析和改进建议：

当前方法的优势 ✅

理解优秀解法：通过阅读和理解最优解，能够学习到更高效的算法思维和编码技巧
主动总结：写题解总结有助于加深印象，避免"一看就会，一做就废"
借助AI辅助：合理利用工具可以提高学习效率

存在的问题 ❌

缺乏独立思考：直接看最优解可能跳过了重要的思考过程
代码质量差：自己写的代码逻辑混乱，说明基础思维训练不足
容易遗忘：看懂≠会用，缺乏足够的练习和复盘

改进建议 💡

分阶段解题法：

先自己思考并实现（哪怕是暴力解法）
尝试优化自己的解法
再对比学习最优解法

代码质量训练：

写完代码后自己先review一遍
尝试重构自己的代码
关注代码的可读性和逻辑清晰度

刻意练习：

对于同类题目，间隔一段时间后再做一遍
总结常见算法模式和解题套路
建立自己的错题本和典型题目集合

深度理解：

不仅要理解"怎么做"，更要理解"为什么这样做"
分析不同解法的时间复杂度和空间复杂度差异

这种学习方法有效但需要调整，关键是要增加自己的思考环节，而不是直接跳到最优解。

唉，以后有思路的还是自己先思考尝试解决吧，哪怕是用最笨拙的方法。对于没有学过的内容，超出知识范围的，像什么链表、二叉树、分治之类的，就直接问AI然后从题目中学习相关的内容。

加载评论中...

力扣面试经典——380题​

📥 输入格式说明​

🔄 逐步执行过程​

1️⃣ 创建对象​

2️⃣ 插入元素 1​

3️⃣ 删除元素 2​

4️⃣ 插入元素 2​

5️⃣ 随机获取元素​

6️⃣ 删除元素 1​

7️⃣ 插入元素 2​

8️⃣ 随机获取元素​

📤 最终输出结果​

💡 关键理解点​

⚠️ 代码语法说明​

🤔 为什么需要哈希表？​

🔧 关于 UT_hash_handle​

❓ 为什么必须包含这个字段？​

📝 总结​

函数逐行解析randomizedSetCreate​

内存布局示意图​

重要设计考虑​

使用示例​

函数逐步解析 randomizedSetInsert​

函数签名解析​

数据结构设计特点​

关键数据结构​

举例解释randomizedSetRemove​

步骤 1: 查找要删除的元素​

步骤 2: 获取索引和最后一个元素​

步骤 3: 用最后一个元素覆盖待删除元素​

步骤 4: 更新最后一个元素在哈希表中的索引​

步骤 5: 从哈希表中删除目标元素并释放内存​

步骤 6: 减少数组大小计数​

为什么用最后一个元素覆盖？​

函数目的​

逐步执行流程​

1. 释放哈希表中所有节点​

2. 释放数组内存​

3. 释放对象本身​

内存管理要点​

释放顺序很重要​

避免内存泄漏​

使用示例​

力扣面试经典——380题

📥 输入格式说明

🔄 逐步执行过程

1️⃣ 创建对象

2️⃣ 插入元素 1

3️⃣ 删除元素 2

4️⃣ 插入元素 2

5️⃣ 随机获取元素

6️⃣ 删除元素 1

7️⃣ 插入元素 2

8️⃣ 随机获取元素

📤 最终输出结果

💡 关键理解点

⚠️ 代码语法说明

🤔 为什么需要哈希表？

🔧 关于 UT_hash_handle

❓ 为什么必须包含这个字段？

📝 总结

函数逐行解析randomizedSetCreate

内存布局示意图

重要设计考虑

使用示例

函数逐步解析 randomizedSetInsert

函数签名解析

数据结构设计特点

关键数据结构

举例解释randomizedSetRemove

步骤 1: 查找要删除的元素

步骤 2: 获取索引和最后一个元素

步骤 3: 用最后一个元素覆盖待删除元素

步骤 4: 更新最后一个元素在哈希表中的索引

步骤 5: 从哈希表中删除目标元素并释放内存

步骤 6: 减少数组大小计数

为什么用最后一个元素覆盖？

函数目的

逐步执行流程

1. 释放哈希表中所有节点

2. 释放数组内存

3. 释放对象本身

内存管理要点

释放顺序很重要

避免内存泄漏

使用示例