力扣381. O(1) 时间插入、删除和获取随机元素 - 允许重复

2024-02-29 11:28

本文主要是介绍力扣381. O(1) 时间插入、删除和获取随机元素 - 允许重复,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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,两者的可能性相同。

提示:

-231 <= val <= 231 - 1
insert, remove 和 getRandom 最多 总共 被调用 2 * 105
当调用 getRandom 时,数据结构中 至少有一个元素

思路:使用hashmap和list联合操作,hashmap存的是集合的值和该值在list中的索引集合,同时定义一个random类用于后续随机获取,n用于记录list元素个数,调用 RandomizedCollection就是初始化刚才的几个东西,然后插入操作的话就是把值加入到list中,加入到map中同时把索引值加到一个集合中,map存值和值对应得索引集合,n++,最后只需返回该值的索引集合大小是否为1就可以知道是否已经在集合中出现过,对于删除操作,如果map没有相应的key就直接返回false,如果map有相应的key的话就要考虑一个事,因为值是存在了list中,list只有删除最后一个元素是O(1)的,所以我们考虑将要删除的值和最后一个值做交换再删除,要删除map和list两处地方,并且删除完后还要更新最后一个元素的索引集合,更新n,对于随机获取元素操作就直接list.get一个random类生成的n范围内随机数字就好

class RandomizedCollection {Map<Integer,Set> index;List<Integer> list;Random random;int n;public RandomizedCollection() {index = new HashMap<>();list = new ArrayList<>();random = new Random();n = 0;}public boolean insert(int val) {Set set = index.getOrDefault(val, new HashSet<>());//存储索引set.add(n);//存储值list.add(val);index.put(val, set);n++;return set.size() == 1;}public boolean remove(int val) {if(!index.containsKey(val)){return false;}else{//只有移除list中最后一个元素才是O(1)int lastIndex = n - 1;//找到list中最后一个元素的索引集合Set lastset = index.get(list.get(lastIndex));//找到要删除元素的索引集合Set set = index.get(val);//利用迭代器获取要删除元素的一个索引int currentIndex = (int)set.iterator().next();//交换要删除元素和最后一个元素swap(list, currentIndex, lastIndex);//删除最后一个元素list.remove(lastIndex);//删除集合中要删除元素的索引set.remove(currentIndex);if(set.size() == 0){index.remove(val);}//修改变换位置后最后一个值的索引lastset.remove(lastIndex);lastset.add(currentIndex);n--;}return true;}public int getRandom() {return list.get(random.nextInt(n));}public void swap(List<Integer> list, int currentIndex, int lastIndex){int tmp = list.get(currentIndex);list.set(currentIndex, list.get(lastIndex));list.set(lastIndex, tmp); }
}/*** 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();*/

这篇关于力扣381. O(1) 时间插入、删除和获取随机元素 - 允许重复的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/758611

相关文章

MySQL逻辑删除与唯一索引冲突解决方案

《MySQL逻辑删除与唯一索引冲突解决方案》本文探讨MySQL逻辑删除与唯一索引冲突问题,提出四种解决方案:复合索引+时间戳、修改唯一字段、历史表、业务层校验,推荐方案1和方案3,适用于不同场景,感兴... 目录问题背景问题复现解决方案解决方案1.复合唯一索引 + 时间戳删除字段解决方案2:删除后修改唯一字

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸(宽高)四、获取页面旋转角度五、判断

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

使用Python删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》:本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

go中的时间处理过程

《go中的时间处理过程》:本文主要介绍go中的时间处理过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 获取当前时间2 获取当前时间戳3 获取当前时间的字符串格式4 相互转化4.1 时间戳转时间字符串 (int64 > string)4.2 时间字符串转时间

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语