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++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

如何利用Java获取当天的开始和结束时间

《如何利用Java获取当天的开始和结束时间》:本文主要介绍如何使用Java8的LocalDate和LocalDateTime类获取指定日期的开始和结束时间,展示了如何通过这些类进行日期和时间的处... 目录前言1. Java日期时间API概述2. 获取当天的开始和结束时间代码解析运行结果3. 总结前言在J

docker如何删除悬空镜像

《docker如何删除悬空镜像》文章介绍了如何使用Docker命令删除悬空镜像,以提高服务器空间利用率,通过使用dockerimage命令结合filter和awk工具,可以过滤出没有Tag的镜像,并将... 目录docChina编程ker删除悬空镜像前言悬空镜像docker官方提供的方式自定义方式总结docker

修改若依框架Token的过期时间问题

《修改若依框架Token的过期时间问题》本文介绍了如何修改若依框架中Token的过期时间,通过修改`application.yml`文件中的配置来实现,默认单位为分钟,希望此经验对大家有所帮助,也欢迎... 目录修改若依框架Token的过期时间修改Token的过期时间关闭Token的过期时js间总结修改若依

java获取图片的大小、宽度、高度方式

《java获取图片的大小、宽度、高度方式》文章介绍了如何将File对象转换为MultipartFile对象的过程,并分享了个人经验,希望能为读者提供参考... 目China编程录Java获取图片的大小、宽度、高度File对象(该对象里面是图片)MultipartFile对象(该对象里面是图片)总结java获取图片

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

Java通过反射获取方法参数名的方式小结

《Java通过反射获取方法参数名的方式小结》这篇文章主要为大家详细介绍了Java如何通过反射获取方法参数名的方式,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、前言2、解决方式方式2.1: 添加编译参数配置 -parameters方式2.2: 使用Spring的内部工具类 -