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

题目:O(1)时间插入、删除和获取随机元素

实现 RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

• 示例 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 。

• 提示：

-231 <= val <= 231 - 1
最多调用 insert、remove 和 getRandom 函数 2 * 105 次
在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

思路

实现 RandomizedSet 类需要使用两个数据结构来满足每个函数的平均时间复杂度为 O(1) 的要求：一个 HashMap 和一个 ArrayList。

• HashMap 用于存储每个元素的值及其在 ArrayList 中的索引，以便实现 O(1) 时间复杂度的插入和删除操作。
• ArrayList 用于存储元素，以便实现 O(1) 时间复杂度的随机访问。

1. **构造函数 RandomizedSet**：初始化 ArrayList 和 HashMap，以及一个随机数生成器 Random。

2. insert(int val) 方法：

   • 检查 val 是否已存在于 HashMap 中。如果不存在，将 val 加入 ArrayList，并在 HashMap 中记录 val 的索引。返回 true。
   • 如果存在，返回 false。

3. remove(int val) 方法：

   • 检查 val 是否存在于 HashMap 中。如果存在，获取 val 的索引。将 val 与 ArrayList 中的最后一个元素交换位置，并更新 HashMap 中最后一个元素的新索引。 移除 ArrayList 中的最后一个元素，并从 HashMap 中删除 val。 返回 true。
   • 如果不存在，返回 false。

4. getRandom() 方法：

   • 使用 Random 生成一个范围在 0 到 ArrayList 大小之间的随机索引，返回对应的元素。

• 时间复杂度:O(1)
• 空间复杂度:O(n)

代码

class RandomizedSet {
    // 用于存储元素的数组
    private ArrayList<Integer> nums;
    // 存储元素值及其在数组中的索引
    private HashMap<Integer, Integer> valToIndex;
    // 随机数生成器
    private Random rand;

    /**
     * 初始化数据结构
     */
    public RandomizedSet() {
        nums = new ArrayList<>();
        valToIndex = new HashMap<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (!valToIndex.containsKey(val)) {
            // 插入元素并记录其在数组中的索引
            valToIndex.put(val, nums.size());
            nums.add(val);
            return true;
        } else {
            return false;
        }
    }

    public boolean remove(int val) {
        if (valToIndex.containsKey(val)) {
            // 插入元素并记录其在数组中的索引
            Integer index = valToIndex.get(val);
            // 获取数组中的最后一个元素
            Integer lastValue = nums.get(nums.size() - 1);

            // 将要删除的元素与最后一个元素交换位置，并更新最后一个元素在 HashMap 中的索引
            nums.set(index, lastValue);
            valToIndex.put(lastValue, index);

            // 移除数组中的最后一个元素，并从 HashMap 中删除该元素
            nums.remove(nums.size() - 1);
            valToIndex.remove(val);
            return true;
        } else {
            return false;
        }
    }

    public int getRandom() {
        // 移除数组中的最后一个元素，并从 HashMap 中删除该元素
        return nums.get(rand.nextInt(nums.size()));
    }
}