LeetCode 第380题：常数时间插入、删除和获取随机元素

📖 文章摘要

本文详细解析LeetCode第380题“常数时间插入、删除和获取随机元素”，这是一道设计题。文章提供了基于哈希表和动态数组的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升数据结构设计能力的读者。

核心知识点： 设计、哈希表、动态数组 难度等级： 中等 推荐人群： 具有基础算法知识，想要提升数据结构设计能力的程序员

题目描述

设计一个支持在平均时间复杂度O(1)下，执行以下操作的数据结构：

1. insert(val)：当元素val不存在时，向集合中插入该项。
2. remove(val)：元素val存在时，从集合中移除该项。
3. getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例

示例 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 表示 1 被成功地插入。
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 - 1
• 最多调用 2 * 10^5 次 insert、remove 和 getRandom
• 在调用 getRandom 方法时，数据结构中至少存在一个元素

解题思路

本题可以使用哈希表和动态数组解决：

1. 使用哈希表存储元素值和其在数组中的索引
2. 使用动态数组存储所有元素
3. insert操作在数组末尾添加元素
4. remove操作将数组末尾元素移到要删除元素的位置
5. getRandom操作随机返回数组中的一个元素

时间复杂度： O(1) 所有操作 空间复杂度： O(n)

图解思路

数据结构设计

数据结构	用途	操作复杂度
HashMap	存储元素值和索引	O(1)
ArrayList	存储所有元素	O(1)

操作流程

操作	步骤	说明
insert	1. 检查哈希表 2. 添加到数组末尾 3. 更新哈希表	插入新元素
remove	1. 检查哈希表 2. 交换元素 3. 更新哈希表	删除元素
getRandom	随机返回数组元素	获取随机元素

代码实现

C# 实现

public class RandomizedSet {
    private Dictionary<int, int> dict;
    private List<int> list;
    private Random random;
    
    public RandomizedSet() {
        dict = new Dictionary<int, int>();
        list = new List<int>();
        random = new Random();
    }
    
    public bool Insert(int val) {
        if (dict.ContainsKey(val)) return false;
        
        dict[val] = list.Count;
        list.Add(val);
        return true;
    }
    
    public bool Remove(int val) {
        if (!dict.ContainsKey(val)) return false;
        
        int lastElement = list[list.Count - 1];
        int index = dict[val];
        
        list[index] = lastElement;
        dict[lastElement] = index;
        
        list.RemoveAt(list.Count - 1);
        dict.Remove(val);
        
        return true;
    }
    
    public int GetRandom() {
        return list[random.Next(list.Count)];
    }
}

Python 实现

class RandomizedSet:
    def __init__(self):
        self.dict = {}
        self.list = []
        
    def insert(self, val: int) -> bool:
        if val in self.dict:
            return False
            
        self.dict[val] = len(self.list)
        self.list.append(val)
        return True
        
    def remove(self, val: int) -> bool:
        if val not in self.dict:
            return False
            
        last_element = self.list[-1]
        index = self.dict[val]
        
        self.list[index] = last_element
        self.dict[last_element] = index
        
        self.list.pop()
        del self.dict[val]
        
        return True
        
    def getRandom(self) -> int:
        return random.choice(self.list)

C++ 实现

class RandomizedSet {
private:
    unordered_map<int, int> dict;
    vector<int> list;
    
public:
    RandomizedSet() {}
    
    bool insert(int val) {
        if (dict.find(val) != dict.end()) return false;
        
        dict[val] = list.size();
        list.push_back(val);
        return true;
    }
    
    bool remove(int val) {
        if (dict.find(val) == dict.end()) return false;
        
        int last_element = list.back();
        int index = dict[val];
        
        list[index] = last_element;
        dict[last_element] = index;
        
        list.pop_back();
        dict.erase(val);
        
        return true;
    }
    
    int getRandom() {
        return list[rand() % list.size()];
    }
};

执行结果

C# 实现

• 执行用时：92 ms
• 内存消耗：24.8 MB

Python 实现

• 执行用时：28 ms
• 内存消耗：13.2 MB

C++ 实现

• 执行用时：4 ms
• 内存消耗：8.4 MB

性能对比

语言	执行用时	内存消耗	特点
C++	4 ms	8.4 MB	执行效率最高，内存占用最小
Python	28 ms	13.2 MB	代码简洁，内存占用适中
C#	92 ms	24.8 MB	类型安全，内存占用较大

代码亮点

1. 🎯 使用哈希表和动态数组优化操作
2. 💡 空间复杂度优化
3. 🔍 处理边界情况
4. 🎨 代码结构清晰，易于维护

常见错误分析

1. 🚫 未处理重复插入
2. 🚫 数据结构选择错误
3. 🚫 边界条件处理错误
4. 🚫 随机性保证问题

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
哈希表+动态数组	O(1)	O(n)	高效，操作简单	空间占用较大
平衡树	O(log n)	O(n)	有序	操作复杂

相关题目

• LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复 - 困难
• LeetCode 146. LRU缓存机制 - 中等
• LeetCode 460. LFU缓存 - 困难

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第380题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！