【C++】每日一题 380 O(1)时间插入,删除和获取随机元素

2024-04-07 11:44

本文主要是介绍【C++】每日一题 380 O(1)时间插入,删除和获取随机元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

实现RandomizedSet 类:

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时,向集合中插入该项,并返回 true ;否则,返回 false 。
bool remove(int val) 当元素 val 存在时,从集合中移除该项,并返回 true ;否则,返回 false 。
int getRandom() 随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素)。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数,并满足每个函数的 平均 时间复杂度为 O(1) 。

#include <unordered_map>
#include <vector>
#include <cstdlib>class RandomizedSet {
private:std::unordered_map<int, int> valToIndex; // 用于存储值到索引的映射std::vector<int> values; // 用于存储集合中的值public:/** 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 (valToIndex.find(val) != valToIndex.end()) {return false; // 如果值已经存在,则返回false}values.push_back(val); // 在向量末尾插入新值valToIndex[val] = values.size() - 1; // 更新值到索引的映射return true;}/** Removes a value from the set. Returns true if the set contained the specified element. */bool remove(int val) {if (valToIndex.find(val) == valToIndex.end()) {return false; // 如果值不存在,则返回false}int index = valToIndex[val]; // 获取值在向量中的索引int lastVal = values.back(); // 获取向量中最后一个值values[index] = lastVal; // 将最后一个值移到被删除的位置valToIndex[lastVal] = index; // 更新最后一个值的索引values.pop_back(); // 删除最后一个值valToIndex.erase(val); // 删除值到索引的映射return true;}/** Get a random element from the set. */int getRandom() {int randomIndex = rand() % values.size(); // 生成随机索引return values[randomIndex]; // 返回随机索引处的值}
};

使用了一个 unordered_map 来存储值到索引的映射,以实现 O(1) 时间复杂度的插入和删除操作。同时,使用一个 vector 来存储集合中的值,并且通过将被删除元素与最后一个元素交换,然后再删除最后一个元素的方式来实现 O(1) 时间复杂度的删除操作。最后,getRandom 函数通过生成一个随机索引来随机返回集合中的一个元素。

易错点:
从 nums 向量中删除特定值 val 对应的元素,并且更新 indices 映射,使得其仍然与 nums 同步。以下代码错误示范

nums.erase(nums.begin()+indices[val]);
indices.erase(val);

假设 indices[val] 给出了 val 在 nums 中的索引位置。第一行代码是从 nums 向量中删除这个索引位置的元素,但是删除后,后面的元素会向前移动填补被删除的位置,这就会导致原来在 indices[val] 位置的元素变成了新的 val,而且 val 在 nums 中的位置已经改变了,所以删除 val 对应的索引值并不正确。

正确的做法是通过交换最后一个元素和要删除的元素来实现删除,然后更新映射。这就是下面的代码片段:

int index = indices[val];
int last = nums.back();
nums[index] = last;
indices[last] = index;
nums.pop_back();
indices.erase(val);

这样做的好处是,它避免了在删除元素后重新排序 nums 向量,同时保持了 indices 映射的正确性。

这篇关于【C++】每日一题 380 O(1)时间插入,删除和获取随机元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

服务器集群同步时间手记

1.时间服务器配置(必须root用户) (1)检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 (2)修改ntp配置文件 [r

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现