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

相关文章

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Vue3组件中getCurrentInstance()获取App实例,但是返回null的解决方案

《Vue3组件中getCurrentInstance()获取App实例,但是返回null的解决方案》:本文主要介绍Vue3组件中getCurrentInstance()获取App实例,但是返回nu... 目录vue3组件中getCurrentInstajavascriptnce()获取App实例,但是返回n

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

SpringMVC获取请求参数的方法

《SpringMVC获取请求参数的方法》:本文主要介绍SpringMVC获取请求参数的方法,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下... 目录1、通过ServletAPI获取2、通过控制器方法的形参获取请求参数3、@RequestParam4、@