【哈希映射】【 哈希集合】 381. O(1) 时间插入、删除和获取随机元素 - 允许重复

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

作者推荐

视频算法专题

本文涉及知识点

哈希映射 哈希集合

LeetCode 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 时,数据结构中 至少有一个 元素

哈希

用向量记录值,追加的时候时间复杂度是O1),删除是O(n)。可以将要删除的元素和尾元素互换,然后删除。
unordered_map<int, unordered_set> m_valueIndex; 记录各值在m_nums中的下标。
注意
要删除的元素就是末尾,要特殊处理。否则会删除下标失败,而多一个下标。

代码

核心代码

class RandomizedCollection {
public:RandomizedCollection() {srand(time(nullptr));std::cout << "==" << std::endl;}bool insert(int val) {bool b = m_valueIndex[val].empty();m_valueIndex[val].emplace(m_nums.size());m_nums.emplace_back(val);std::cout << m_nums.size() << std::endl;return b;}bool remove(int val) {if (m_valueIndex[val].empty()){return false;}const int delIndex = *m_valueIndex[val].begin();m_valueIndex[val].erase(m_valueIndex[val].begin());const int endValue = m_nums.back();if (m_valueIndex[endValue].count(m_nums.size() - 1)){m_valueIndex[endValue].erase(m_nums.size() - 1);m_valueIndex[endValue].emplace(delIndex);m_nums[delIndex] = endValue;}m_nums.pop_back();std::cout << "del " << m_nums.size() << std::endl;return true;}int getRandom() {std::cout << "getRandom " << m_nums.size() << std::endl;return m_nums[rand() % m_nums.size()];}unordered_map<int, unordered_set<int>> m_valueIndex;vector<int> m_nums;
};

2023年5月

class RandomizedCollection {
public:
RandomizedCollection() {
srand(time(nullptr));
}
bool insert(int val) {
m_mValueIndexs[val].emplace(m_iSize);
m_arr[m_iSize] = val;
m_iSize++;
return 1 == m_mValueIndexs[val].size();
}
bool remove(int val) {
if (m_mValueIndexs.count(val))
{
int index = *m_mValueIndexs[val].begin();
m_mValueIndexs[val].erase(index);
Erase(index);
if (m_mValueIndexs[val].empty())
{
m_mValueIndexs.erase(val);
}
return true;
}
return false;
}
int getRandom() {
int index = rand() % m_iSize;
return m_arr[index];
}
void Erase(int index)
{
if (m_iSize - 1 == index)
{
m_iSize–;
return;
}
const int iEndValue = m_arr[m_iSize - 1];
m_mValueIndexs[iEndValue].erase(m_iSize - 1);
m_mValueIndexs[iEndValue].insert(index);
std::swap(m_arr[m_iSize - 1], m_arr[index]);
m_iSize–;
}
std::unordered_map<int, std::unordered_set> m_mValueIndexs;
int m_arr[1000 * 200];
int m_iSize = 0;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 **C+

+17**
如无特殊说明,本算法用**C++**实现。

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



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

相关文章

python获取网页表格的多种方法汇总

《python获取网页表格的多种方法汇总》我们在网页上看到很多的表格,如果要获取里面的数据或者转化成其他格式,就需要将表格获取下来并进行整理,在Python中,获取网页表格的方法有多种,下面就跟随小编... 目录1. 使用Pandas的read_html2. 使用BeautifulSoup和pandas3.

SpringBoot UserAgentUtils获取用户浏览器的用法

《SpringBootUserAgentUtils获取用户浏览器的用法》UserAgentUtils是于处理用户代理(User-Agent)字符串的工具类,一般用于解析和处理浏览器、操作系统以及设备... 目录介绍效果图依赖封装客户端工具封装IP工具实体类获取设备信息入库介绍UserAgentUtils

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

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

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

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

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.

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"文

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

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

SpringMVC获取请求参数的方法

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