【LeetCode 面试经典150题】380. Insert Delete GetRandom O(1) O(1) 时间插入、删除和获取随机元素

380. Insert Delete GetRandom O(1)

题目大意

Implement the RandomizedSet class:

• RandomizedSet() Initializes the RandomizedSet object.
• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
  You must implement the functions of the class such that each function works in average O(1) time complexity.

中文释义

实现 RandomizedSet 类：

• RandomizedSet() 初始化 RandomizedSet 对象。
• bool insert(int val) 将一个元素 val 插入集合中，如果不存在则插入。如果元素不存在返回 true，否则返回 false。
• bool remove(int val) 从集合中移除一个元素 val，如果存在则移除。如果元素存在返回 true，否则返回 false。
• int getRandom() 从当前集合中返回一个随机元素（保证调用这个方法时集合中至少有一个元素）。每个元素被返回的概率相同。
  你必须实现类的函数，使得每个函数的平均时间复杂度为 O(1)。

Example

Example 1:

• Input:
  • ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
  • [[], [1], [2], [2], [], [1], [2], []]
• Output: [null, true, false, true, 2, true, false, 2]
• Explanation:
  • RandomizedSet randomizedSet = new RandomizedSet();
  • randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
  • randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
  • randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
  • randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
  • randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
  • randomizedSet.insert(2); // 2 was already in the set, so return false.
  • randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints

• -2^31 <= val <= 2^31 - 1
• At most 2 * 10^5 calls will be made to insert, remove, and getRandom.
• There will be at least one element in the data structure when getRandom is called.

解题思路

算法描述

实现 RandomizedSet 类，该类支持在平均 O(1) 时间复杂度内执行插入、删除和获取随机元素的操作。算法的关键点在于使用一个哈希表和一个动态数组来有效地管理元素。具体实现步骤如下：

1. 初始化:

   • 使用一个 unordered_map（哈希表）valueIndexMap 来存储每个元素及其在数组中的索引。
   • 使用一个 vector（动态数组）values 来存储集合中的元素。

2. 插入操作 (insert 方法):

   • 首先检查要插入的元素是否已存在于哈希表中。如果已存在，返回 false。
   • 如果不存在，将元素添加到数组的末尾，并在哈希表中更新该元素的索引。

3. 删除操作 (remove 方法):

   • 首先检查要删除的元素是否存在于哈希表中。如果不存在，返回 false。
   • 如果存在，找到该元素在数组中的索引。将数组中的最后一个元素移动到这个索引处，并更新哈希表中的索引。
   • 删除数组的最后一个元素，并从哈希表中移除原始元素。

4. 获取随机元素 (getRandom 方法):

   • 使用 rand() 函数生成一个数组索引的随机数。
   • 返回数组中该随机索引对应的元素。

代码实现

class RandomizedSet {
    std::unordered_map<int, int> valueIndexMap;
    std::vector<int> values;

public:
    RandomizedSet() {}

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

    bool remove(int val) {
        if (valueIndexMap.find(val) == valueIndexMap.end()) {
            return false;
        }
        int lastVal = values.back();
        int idx = valueIndexMap[val];
        values[idx] = lastVal;
        valueIndexMap[lastVal] = idx;
        values.pop_back();
        valueIndexMap.erase(val);
        return true;
    }

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