Insert Delete GetRandom O(1),LeetCode,380

LeetCode 上的第 380 题 “Insert Delete GetRandom O(1)” 是一个设计数据结构的问题，要求实现一个数据结构，支持以下操作，并且每个操作的时间复杂度都是 O(1)：

1. insert(val)：当元素 val 不存在时，向集合中插入该项。
2. remove(val)：当元素 val 存在时，从集合中移除该项。
3. getRandom()：随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有相同的概率被返回。

解决思路

要实现这三个操作的时间复杂度都是 O(1)，我们需要结合哈希表和数组的特点：

1. 哈希表：用于快速查找和删除元素，时间复杂度为 O(1)。
2. 数组：用于快速随机访问元素，时间复杂度为 O(1)。

具体实现如下：

• 使用一个哈希表 unordered_map 来存储每个元素值及其在数组中的索引。
• 使用一个动态数组 vector 来存储所有元素。

操作实现

1. 插入操作 (insert(val))：
   • 检查哈希表中是否已经存在该元素，如果存在则直接返回 false。
   • 将元素插入到数组的末尾，并在哈希表中记录该元素的索引。
   • 返回 true。
2. 删除操作 (remove(val))：
   • 检查哈希表中是否已经存在该元素，如果不存在则直接返回 false。
   • 从哈希表中获取该元素的索引，然后将数组末尾的元素移动到该索引位置，并更新哈希表中末尾元素的索引。
   • 删除数组末尾的元素，并从哈希表中删除该元素。
   • 返回 true。
3. 随机访问操作 (getRandom())：
   • 直接从数组中随机选择一个元素返回。

代码实现

#include #include #include #include

bool insert(int val) {
    if (hash.find(val) != hash.end()) {
        return false;
    }
    nums.push_back(val);
    hash[val] = nums.size() - 1;
    return true;
}

bool remove(int val) {
    if (hash.find(val) == hash.end()) {
        return false;
    }
    int last = nums.back();
    int idx = hash[val];
    nums[idx] = last;
    hash[last] = idx;
    nums.pop_back();
    hash.erase(val);
    return true;
}

int getRandom() {
    int randomIndex = rand() % nums.size();
    return nums[randomIndex];
}

• Your RandomizedSet object will be instantiated and called as such:
• RandomizedSet* obj = new RandomizedSet();
• bool param_1 = obj->insert(val);
• bool param_2 = obj->remove(val);
• int param_3 = obj->getRandom(); */

  解释

  • 构造函数：初始化随机数种子，以便在 getRandom() 中使用。
  • 插入操作：首先检查元素是否已存在，如果不存在则插入到数组和哈希表中。
  • 删除操作：首先检查元素是否已存在，如果存在则通过交换数组中的元素和更新哈希表来实现 O(1) 的删除。
  • 随机访问操作：直接从数组中随机选择一个元素返回。

这种设计确保了每个操作的时间复杂度都是 O(1)，同时利用了哈希表和数组的各自优势。