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

LeetCode题练习与总结:O(1) 时间插入、删除和获取随机元素 - 允许重复--381

一、题目描述

RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素,以及删除随机元素。

实现 RandomizedCollection 类:

  • RandomizedCollection()初始化空的 RandomizedCollection 对象。
  • bool insert(int val) 将一个 val 项插入到集合中,即使该项已经存在。如果该项不存在,则返回 true ,否则返回 false 。
  • bool remove(int val) 如果存在,从集合中移除一个 val 项。如果该项存在,则返回 true ,否则返回 false 。注意,如果 val 在集合中出现多次,我们只删除其中一个。
  • int getRandom() 从当前的多个元素集合中返回一个随机元素。每个元素被返回的概率与集合中包含的相同值的数量 线性相关 。

您必须实现类的函数,使每个函数的 平均 时间复杂度为 O(1) 。

注意:生成测试用例时,只有在 RandomizedCollection 中 至少有一项 时,才会调用 getRandom 。

示例 1:

输入
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
输出
[null, true, false, true, 2, true, 1]

解释
RandomizedCollection collection = new RandomizedCollection();// 初始化一个空的集合。
collection.insert(1);   // 返回 true,因为集合不包含 1。
                        // 将 1 插入到集合中。
collection.insert(1);   // 返回 false,因为集合包含 1。
                        // 将另一个 1 插入到集合中。集合现在包含 [1,1]。
collection.insert(2);   // 返回 true,因为集合不包含 2。
                        // 将 2 插入到集合中。集合现在包含 [1,1,2]。
collection.getRandom(); // getRandom 应当:
                        // 有 2/3 的概率返回 1,
                        // 1/3 的概率返回 2。
collection.remove(1);   // 返回 true,因为集合包含 1。
                        // 从集合中移除 1。集合现在包含 [1,2]。
collection.getRandom(); // getRandom 应该返回 1 或 2,两者的可能性相同。

提示:

  • -2^31 <= val <= 2^31 - 1
  • insertremove 和 getRandom 最多 总共 被调用 2 * 10^5 次
  • 当调用 getRandom 时,数据结构中 至少有一个 元素

二、解题思路

为了实现 RandomizedCollection 类,我们需要保证 insertremove 和 getRandom 三个操作的时间复杂度都是 O(1)。以下是一种可能的解题思路:

  1. 使用 HashMap<Integer, Set<Integer>> 来存储每个值对应的索引集合。键是集合中的值,值是该值在动态数组中出现的所有索引的集合。
  2. 使用动态数组(如 ArrayList)来存储集合中的所有元素。
  3. 在插入操作时,将元素添加到动态数组末尾,并在哈希表中记录该元素的索引。
  4. 在删除操作时,找到要删除元素的索引,并将其与动态数组中最后一个元素交换,然后删除最后一个元素。更新哈希表中对应元素的索引集合。
  5. 在获取随机元素操作时,只需从动态数组中随机选择一个索引,然后返回该索引对应的元素。

三、具体代码

import java.util.*;

class RandomizedCollection {
    Map<Integer, Set<Integer>> idx;
    List<Integer> nums;

    public RandomizedCollection() {
        idx = new HashMap<>();
        nums = new ArrayList<>();
    }
    
    public boolean insert(int val) {
        boolean isNotExist = !idx.containsKey(val);
        if (isNotExist) idx.put(val, new HashSet<>());
        idx.get(val).add(nums.size());
        nums.add(val);
        return isNotExist;
    }
    
    public boolean remove(int val) {
        if (!idx.containsKey(val) || idx.get(val).isEmpty()) return false;
        int removeIdx = idx.get(val).iterator().next();
        idx.get(val).remove(removeIdx);
        if (removeIdx < nums.size() - 1) {
            int lastVal = nums.get(nums.size() - 1);
            nums.set(removeIdx, lastVal);
            idx.get(lastVal).remove(nums.size() - 1);
            idx.get(lastVal).add(removeIdx);
        }
        nums.remove(nums.size() - 1);
        if (idx.get(val).isEmpty()) idx.remove(val);
        return true;
    }
    
    public int getRandom() {
        Random rand = new Random();
        return nums.get(rand.nextInt(nums.size()));
    }
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

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

1. 时间复杂度
  • insert(int val) 方法:

    • 检查元素是否存在于哈希表中:O(1)
    • 如果元素不存在,将其加入哈希表:O(1)
    • 将元素的索引加入对应的集合:O(1)
    • 将元素添加到列表的末尾:O(1)
    • 因此,insert 方法的时间复杂度是 O(1)。
  • remove(int val) 方法:

    • 检查元素是否存在于哈希表中:O(1)
    • 获取元素集合中的任意一个索引:O(1)
    • 将该索引从集合中移除:O(1)
    • 如果移除的不是最后一个元素,则与最后一个元素交换:O(1)
    • 移除列表中的最后一个元素:O(1)
    • 因此,remove 方法的时间复杂度是 O(1)。
  • getRandom() 方法:

    • 生成一个随机索引:O(1)
    • 根据索引从列表中获取元素:O(1)
    • 因此,getRandom 方法的时间复杂度是 O(1)。
2. 空间复杂度
  • idx(哈希表):

    • 假设集合中最多有 n 个不同的元素,每个元素最多出现 m 次。
    • 哈希表中存储每个元素及其索引集合,因此空间复杂度为 O(n * m)。
  • nums(动态数组):

    • 动态数组存储了集合中的所有元素,因此空间复杂度为 O(n * m)。
  • 整体空间复杂度:

    • 综合考虑 idx 和 nums 的空间复杂度,整体空间复杂度为 O(n * m),其中 n 是不同元素的数量,m 是每个元素的平均出现次数。
3. 总结
  • 时间复杂度:

    • insert(int val): O(1)
    • remove(int val): O(1)
    • getRandom(): O(1)
  • 空间复杂度: O(n * m),其中 n 是不同元素的数量,m 是每个元素的平均出现次数。在极端情况下,如果每个元素只出现一次,则空间复杂度简化为 O(n)。

五、总结知识点

  • 类定义:

    • 定义了一个名为 RandomizedCollection 的类,该类包含三个方法:insertremove, 和 getRandom
  • 成员变量:

    • idx: 一个 HashMap,用于存储每个整数值及其在动态数组 nums 中的索引集合。
    • nums: 一个 ArrayList,用于存储集合中的所有元素。
  • 构造函数:

    • RandomizedCollection(): 类的构造函数,用于初始化成员变量 idx 和 nums
  • 哈希表(HashMap):

    • 用于快速查找元素是否存在于集合中,以及获取元素的所有索引。
    • HashMap 的键是集合中的整数值,值是一个 HashSet,存储了该整数值在 nums 中的所有索引。
  • 动态数组(ArrayList):

    • 用于存储集合中的所有元素,支持快速添加和删除操作。
  • 集合(HashSet):

    • 用于存储索引,保证了索引的唯一性,并且提供了 O(1) 时间复杂度的删除操作。
  • 插入操作:

    • insert(int val): 将元素添加到集合中,如果元素不存在则返回 true,否则返回 false
  • 删除操作:

    • remove(int val): 从集合中删除指定的元素,如果元素存在则返回 true,否则返回 false
    • 使用了集合中的迭代器来获取要删除元素的索引。
    • 删除时,如果元素不是最后一个,则将其与最后一个元素交换,然后删除最后一个元素,这样可以保证 O(1) 时间复杂度的删除操作。
  • 随机访问:

    • getRandom(): 返回集合中的随机元素。
    • 使用了 Random 类来生成随机数,然后通过随机数索引从 nums 中获取元素。
  • 迭代器:

    • 在 remove 方法中,使用了 HashSet 的迭代器来获取要删除元素的索引。
  • 条件判断:

    • 在 insert 和 remove 方法中,使用了条件判断来确定元素是否存在以及是否需要更新哈希表。
  • 方法返回值:

    • insert 和 remove 方法返回一个布尔值,表示操作是否成功。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。


http://www.kler.cn/a/383178.html

相关文章:

  • 【ROS2】坐标TF变换工具-tf2_ros
  • React 前端框架简介
  • C/C++基础知识复习(43)
  • Java - 日志体系_Apache Commons Logging(JCL)日志接口库
  • Spring(三)-SpringWeb-概述、特点、搭建、运行流程、组件、接受请求、获取请求数据、特殊处理、拦截器
  • 门户系统需要压测吗?以及门户系统如何压力测试?
  • Air780E基于LuatOS编程开发
  • web实操3——servlet
  • 短剧APP系统开发,数字化微短剧时代
  • SpringBoot框架学习总结 及 整合 JDBC Mybatis-plus JPA Redis 我的学习笔记
  • 《Qwen2-VL》论文精读【下】:发表于2024年10月 Qwen2-VL 迅速崛起 | 性能与GPT-4o和Claude3.5相当
  • 《Java 实现选择排序:原理剖析与代码详解》
  • 手动切换python版本
  • yolov8涨点系列之Concat模块改进
  • 300公斤载重橡胶履带式无人车底盘技术详解
  • AUTOSAR CP NVRAM Manager规范导读
  • Angular 中 UntypedFormGroup和FormGroup的区别?
  • 【python】游戏设计 --- 双人井字棋小游戏
  • OceanBase中,如何解读 obdiag 收集的火焰图 【DBA早下班系列】
  • 刷题强训 (day1) -- 数字统计
  • 软件工程笔记一
  • Redis 数据类型详解与应用
  • 加密货币行业与2024年美国大选
  • Linux sudo命令及权限设置
  • 【MongoDB】MongoDB的Java API及Spring集成(Spring Data)
  • 免费送源码:Java+springboot+MySQL springboot 线上线下一体化的宠物交易 计算机毕业设计原创定制