2021-08-19 380. O(1) 时间插入、删除和获取随机元素(哈希表+动态数组)

2024-03-10 21:18

本文主要是介绍2021-08-19 380. O(1) 时间插入、删除和获取随机元素(哈希表+动态数组),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

注:

题目:
设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。

insert(val):当元素 val 不存在时,向集合中插入该项。
remove(val):元素 val 存在时,从集合中移除该项。
getRandom:随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);// 返回 false ,表示集合中不存在 2 。
randomSet.remove(2);// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();// 从集合中移除 1 ,返回 true 。集合现在包含 [2] 。
randomSet.remove(1);// 2 已在集合中,所以返回 false 。
randomSet.insert(2);// 由于 2 是集合中唯一的数字,getRandom 总是返回 2 。
randomSet.getRandom();

题解:
解题思路
觉得有点用的盆友们点个赞呗(创作不易,卑微求赞

直接说重点,本题的核心思想是利用动态数组的下标索引实现常数时间内的插入和随机元素的访问,再利用哈希表实现常数时间的删除操作。
在这里插入图片描述

1. 插入元素 insert(val)
将元素放入vector中,使用push_back(val)函数。
把元素和下标一起放入哈希表,使用hash[val] = dyArray.size() - 1.

2. 删除元素 remove(val)
如果直接在vector中删除某个元素,会引起后续元素的大幅度移动,从而导致对hash进行大量的修改。

为了实现常量时间,我们选择将要删除的元素调换到最后一位,再使用vector的pop_back()方法进行删除。

这里需要注意,要同步修改哈希表中的元素!使用erase(val) 删除元素的键值对,同时还要修改原先在最后一位,被调换到前面的元素的对应下标!
在这里插入图片描述

3. 随机返回 getRandom()
直接产生随机数,对vector.size()取模,就可以得到从 0 到 size-1 的随机数了!

复杂度分析
时间复杂度:O(n)
空间复杂度:O(n)

class RandomizedSet {
public:vector<int> nums;map<int,int> num_index;/** Initialize your data structure here. */RandomizedSet() {}/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */bool insert(int val) {if(num_index.count(val)==1){return false;}else{num_index[val]=nums.size();nums.push_back(val);}return true;}/** Removes a value from the set. Returns true if the set contained the specified element. */bool remove(int val) {if(num_index.count(val)==0){return false;}else{int index=num_index[val];int maxindex=nums.size()-1;nums[index]=nums[maxindex];num_index[nums[index]]=index;nums.pop_back();num_index.erase(val);}return true;}/** Get a random element from the set. */int getRandom() {int index=rand()%(nums.size());return nums[index];}
};/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet* obj = new RandomizedSet();* bool param_1 = obj->insert(val);* bool param_2 = obj->remove(val);* int param_3 = obj->getRandom();*/

这篇关于2021-08-19 380. O(1) 时间插入、删除和获取随机元素(哈希表+动态数组)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

使用Python实现获取网页指定内容

《使用Python实现获取网页指定内容》在当今互联网时代,网页数据抓取是一项非常重要的技能,本文将带你从零开始学习如何使用Python获取网页中的指定内容,希望对大家有所帮助... 目录引言1. 网页抓取的基本概念2. python中的网页抓取库3. 安装必要的库4. 发送HTTP请求并获取网页内容5. 解