当前位置：首页 > article >正文

LeetCode题练习与总结：O(1) 时间插入、删除和获取随机元素--380

article 2024/11/7 10:35:17

一、题目描述

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(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
最多调用 insert、remove 和 getRandom 函数 2 * 10^5 次
在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

二、解题思路

为了实现 RandomizedSet 类，我们需要保证 insert、remove 和 getRandom 操作的平均时间复杂度为 O(1)。为了达到这个目标，我们可以使用以下数据结构：

动态数组（ArrayList）：用于存储集合中的元素，这样可以在 O(1) 时间内通过索引访问到任何元素。
哈希表（HashMap）：用于存储每个元素值与其在动态数组中索引的映射，这样可以在 O(1) 时间内检查元素是否存在以及获取其索引。

以下是解题思路：

插入操作（insert）：
- 使用哈希表检查元素是否已存在。
- 如果不存在，将其添加到动态数组的末尾，并在哈希表中记录其索引。
删除操作（remove）：
- 使用哈希表检查元素是否存在以及其索引。
- 如果存在，将数组中该元素与最后一个元素交换位置，然后删除数组末尾的元素，并更新哈希表中的索引映射。
获取随机元素（getRandom）：
- 由于数组中的元素是连续存储的，我们可以通过生成一个随机索引来直接访问数组中的随机元素。

三、具体代码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class RandomizedSet {
    private Map<Integer, Integer> indexMap;
    private List<Integer> nums;
    private Random rand;

    public RandomizedSet() {
        indexMap = new HashMap<>();
        nums = new ArrayList<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        if (indexMap.containsKey(val)) {
            return false;
        }
        indexMap.put(val, nums.size());
        nums.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (!indexMap.containsKey(val)) {
            return false;
        }
        int lastElement = nums.get(nums.size() - 1);
        int idxToRemove = indexMap.get(val);
        nums.set(idxToRemove, lastElement);
        indexMap.put(lastElement, idxToRemove);
        nums.remove(nums.size() - 1);
        indexMap.remove(val);
        return true;
    }
    
    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }
}

这段代码实现了 RandomizedSet 类，满足了题目要求的 O(1) 时间复杂度。每次插入和删除操作都会更新哈希表和动态数组，而获取随机元素则直接从动态数组中随机选择一个索引。

四、时间复杂度和空间复杂度

1. 时间复杂度

构造函数 RandomizedSet():
- 初始化 indexMap 和 nums 的时间复杂度是 O(1)。
- 初始化 rand 的时间复杂度也是 O(1)。
- 因此，总的时间复杂度是 O(1)。
方法 insert(int val):
- 检查元素是否存在于哈希表中，时间复杂度是 O(1)。
- 如果元素不存在，则添加到动态数组和哈希表中，添加到数组和哈希表的操作时间复杂度都是 O(1)。
- 因此，总的时间复杂度是 O(1)。
方法 remove(int val):
- 检查元素是否存在于哈希表中，时间复杂度是 O(1)。
- 如果元素存在，则需要交换待删除元素与数组末尾元素的位置，并更新哈希表，这些操作的时间复杂度都是 O(1)。
- 删除数组末尾元素，时间复杂度是 O(1)。
- 从哈希表中删除元素，时间复杂度也是 O(1)。
- 因此，总的时间复杂度是 O(1)。
方法 getRandom():
- 生成随机索引，时间复杂度是 O(1)。
- 通过索引访问数组元素，时间复杂度是 O(1)。
- 因此，总的时间复杂度是 O(1)。

2. 空间复杂度

构造函数 RandomizedSet():
- indexMap 和 nums 都是动态数据结构，它们的空间复杂度取决于集合中元素的数量。
- rand 是一个轻量级的对象，它占用的空间可以认为是 O(1)。
- 因此，总的空间复杂度是 O(n)，其中 n 是集合中元素的数量。
方法 insert(int val):
- 没有使用额外的空间，除了在 nums 和 indexMap 中存储元素。
- 因此，空间复杂度是 O(1)。
方法 remove(int val):
- 同样，没有使用额外的空间。
- 因此，空间复杂度是 O(1)。
方法 getRandom():
- 没有使用额外的空间。
- 因此，空间复杂度是 O(1)。

3. 总结

时间复杂度:
- 构造函数：O(1)
- insert(int val)：O(1)
- remove(int val)：O(1)
- getRandom()：O(1)
空间复杂度:
- 构造函数：O(n)
- insert(int val)：O(1)
- remove(int val)：O(1)
- getRandom()：O(1)

其中 n 是集合中元素的数量。注意，虽然单个操作的空间复杂度是 O(1)，但是随着集合中元素数量的增加，整体空间需求会线性增长。

五、总结知识点

类定义:
- public class RandomizedSet 定义了一个公共类 RandomizedSet。
成员变量:
- private Map<Integer, Integer> indexMap; 定义了一个私有成员变量 indexMap，用于存储元素值与其在动态数组中的索引的映射。
- private List<Integer> nums; 定义了一个私有成员变量 nums，用于存储集合中的元素。
- private Random rand; 定义了一个私有成员变量 rand，用于生成随机数。
构造函数:
- public RandomizedSet() 是类的构造函数，用于初始化成员变量。
哈希表（HashMap）:
- indexMap 是一个 HashMap，它提供了 O(1) 时间复杂度的查找、插入和删除操作。
动态数组（ArrayList）:
- nums 是一个 ArrayList，它支持动态数组操作，如添加、删除和通过索引访问元素。
随机数生成（Random）:
- rand 是 Random 类的一个实例，用于生成随机数。
方法定义:
- public boolean insert(int val) 定义了一个公共方法，用于向集合中插入一个元素。
- public boolean remove(int val) 定义了一个公共方法，用于从集合中移除一个元素。
- public int getRandom() 定义了一个公共方法，用于从集合中随机获取一个元素。
条件判断:
- if (indexMap.containsKey(val)) 用于检查元素是否已经在集合中。
- if (!indexMap.containsKey(val)) 用于检查元素是否不在集合中。
哈希表操作:
- indexMap.put(val, nums.size()); 将元素值和其在数组中的索引插入哈希表。
- indexMap.remove(val); 从哈希表中移除一个元素。
数组操作:
- nums.add(val); 在数组的末尾添加一个元素。
- nums.set(idxToRemove, lastElement); 通过索引设置数组中的元素。
- nums.remove(nums.size() - 1); 移除数组末尾的元素。
随机数的使用:
- rand.nextInt(nums.size()); 生成一个介于 0（包含）和 nums.size()（不包含）之间的随机整数，用于随机访问数组元素。
返回值:
- return true; 和 return false; 分别用于表示操作成功或失败。
- return nums.get(rand.nextInt(nums.size())); 返回一个随机选择的数组元素。