Insert Delete Get Random

380. 时间插入、删除和获取随机元素

分析

插入操作：
- 可以使用一个哈希表来存储元素及其索引，这样可以在 O(1) 时间内检查元素是否存在，并在数组末尾插入新元素
删除操作：
- 对于删除操作，不直接从哈希表中删除元素，而是用数组末尾的元素替代被删除的元素。这样可以在 O(1) 时间内移除元素，而不需要移动数组中的其它元素
随机访问操作：
- 使用一个数组来存储所有元素，借助数组的随机访问特性，可以在 O(1) 时间内获取一个随机元素

时间复杂度

insert(val)：哈希表的查找和插入操作都是 O(1)，数组的末尾插入也是 O(1)
remove(val)：删除操作中的查找、替换和哈希表更新都是 O(1)，数组末尾删除是 O(1)
getRandom()：通过 rand() 和数组索引的方式随机获取元素是 O(1)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


class RandomizedSet
{
public:
    std::unordered_map<int, int> hash;  // 存储元素及其索引
    std::vector<int> nums;  // 存储元素，支持随机访问

    // 初始化 RandomizedSet 对象
    RandomizedSet() {}

    // 插入元素 val
    bool insert(int val)
    {
        if (hash.count(val) == 0)
        {
            nums.push_back(val);  // 将 val 加入 nums 数组
            hash[val] = nums.size() - 1;  // 记录 val 在 nums 数组中的索引
            return true;
        }
        return false;
    }

    // 移除元素 val
    bool remove(int val)
    {
        if (hash.count(val))
        {
            int tail = nums.back();  // 获取数组末尾的元素
            int val_index = hash[val];  // 获取 val 在 nums 数组中的索引
            int tail_index = hash[tail];  // 获取数组末尾元素的索引

            // 将 val 和数组末尾元素交换
            std::swap(nums[val_index], nums[tail_index]);
            std::swap(hash[val], hash[tail]);

            nums.pop_back();  // 移除数组末尾元素
            hash.erase(val);  // 从哈希表中移除 val
            return true;
        }
        return false;
    }

    // 随机返回一个元素
    int getRandom()
    {
        return nums[rand() % nums.size()];  // 随机返回 nums 数组中的一个元素
    }
};