LeetCode-380. O(1) 时间插入、删除和获取随机元素【哈希表,动态数组,随机数】
题目描述:
实现RandomizedSet 类:
RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时,向集合中插入该项,并返回 true ;否则,返回 false 。
bool remove(int val) 当元素 val 存在时,从集合中移除该项,并返回 true ;否则,返回 false 。
int getRandom() 随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素)。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数,并满足每个函数的 平均 时间复杂度为 O(1) 。
示例:
输入
[“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]
解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ,表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ,返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中,所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字,getRandom 总是返回 2 。
提示:
-231 <= val <= 231 - 1
最多调用 insert、remove 和 getRandom 函数 2 * 105 次
在调用 getRandom 方法时,数据结构中 至少存在一个 元素。
解题思路一:3个函数insert,remove,getRandom
哈希表实现remove操作O(1):哈希表为<元素值,对应下标>
- 删除vector中值为val的元素,获取val值在vector中的位置(可以通过哈希表O(1)),将val与vector中的最后一个元素交换(交换是O(1)),删除最后一个元素(也是O(1))。
- 更新交换元素的下标,删除val对应的项
vector实现insert和grtRandom操作O(1)
- insert直接加到数组最后,并且更新哈希表。
- getRandom拿到随机数,对数组大小取模即可。
class RandomizedSet {
private:
unordered_map<int,int> hash;//哈希表为<元素值,对应下标>,为了实现remove操作O(1)。
vector<int> v;//vector实现getRandom和insert操作的O(1)
public:
RandomizedSet() {
srand((unsigned)time(NULL));
}
bool insert(int val) {
if(hash.count(val)) return false;//代表v中存在val直接返回
v.emplace_back(val);
hash[val] = v.size() - 1;//记录对应下标
return true;
}
bool remove(int val) {
if(!hash.count(val)) return false;//如果哈希表中不存在val,返回false
int lastPos = v.size() - 1;//将val值和数组最后一个元素进行交换
int valPos = hash[val];
v[valPos] = v[lastPos];//交换
v.pop_back();//vector数组删除val
hash[v[valPos]] = valPos;//被交换的值下标发生变化,需要更新
hash.erase(val);//哈希表中删除val对应的项
return true;
}
int getRandom() {
//对下标产生随机数
return v[rand()%v.size()];
}
};
/**
* 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();
*/
知识点:
- hash.find(val)== hash.end()。代表哈希表中不存在val值,相应的!=则说明存在val值对应的项。或者用hash.count();1代表有,0代表无
- hash.erase(val);直接删除val对应的项
- 取得(0,x)的随机整数:rand()%x;
取得(a,b)的随机整数:rand()%(b-a);
取得[a,b)的随机整数:rand()%(b-a)+a;
取得[a,b]的随机整数:rand()%(b-a+1)+a;
取得(a,b]的随机整数:rand()%(b-a)+a+1;
取得0-1之间的浮点数:rand()/double(RAND_MAX)。 - srand()函数
srand()可用来设置rand()产生随机数时的随机数种子。通过设置不同的种子,我们可以获取不同的随机数序列。可以利用srand((unsigned int)(time(NULL))的方法,利用系统时钟,产生不同的随机数种子。不过要调用time(),需要加入头文件< ctime >。
srand((unsigned)time(NULL));//若不使用srand的话,rand()其实产生的一直是一个数。
cout<<rand()<<endl;
解题思路二:
class RandomizedSet {
public:
RandomizedSet() {
srand((unsigned)time(NULL));
}
bool insert(int val) {
if (indices.count(val)) {
return false;
}
int index = nums.size();//注意这里是先获取nums的size()再emplace_back的
nums.emplace_back(val);
indices[val] = index;//这里的index是添加元素之前的最后一个位置,所以不用减1
return true;
}
bool remove(int val) {
if (!indices.count(val)) {
return false;
}
int index = indices[val];
int last = nums.back();
nums[index] = last;
indices[last] = index;
nums.pop_back();
indices.erase(val);
return true;
}
int getRandom() {
int randomIndex = rand()%nums.size();
return nums[randomIndex];
}
private:
vector<int> nums;
unordered_map<int, int> indices;
};
复杂度分析
时间复杂度:初始化和各项操作的时间复杂度都是 O(1)。
空间复杂度:O(n),其中 nn 是集合中的元素个数。存储元素的数组和哈希表需要 O(n) 的空间。
链接:https://leetcode-cn.com/problems/insert-delete-getrandom-o1/solution/o1-shi-jian-cha-ru-shan-chu-he-huo-qu-su-rlz2/
相关文章
- ☆打卡算法☆LeetCode 209. 长度最小的子数组 算法解析
- ☆打卡算法☆LeetCode 225. 用队列实现栈 算法解析
- Leetcode 差分数组的应用「建议收藏」
- Array相关LeetCode题目笔记
- LeetCode周赛292,800多人做出第四题,大佬怒喷太简单……
- leetcode-26删除有序数组中的重复项(双指针)「建议收藏」
- Leetcode 题目927-三等分0和1组成的数组
- leetcode 136. 只出现一次的数字 js 实现
- LeetCode:122. 买卖股票的最佳时机 II
- LeetCode 104. 二叉树的最大深度
- LeetCode 561. 数组拆分 I
- LeetCode 66. 加一
- LeetCode 2197. 替换数组中的非互质数(栈)
- LeetCode 2195. 向数组中追加 K 个整数(贪心)
- leetcode刷题(122)——62. 不同路径
- 【day08】LeetCode(力扣)每日一刷[409. 最长回文串 ][144. 二叉树的前序遍历][589. N 叉树的前序遍历 ]
- js刷LeetCode拿offer之滑动窗口
- javascript分类刷leetcode动态规划篇
- LeetCode - #74 搜索二维矩阵
- JavaScript刷LeetCode模板技巧篇(一)2
- LeetCode 26:删除有序数组中的重复项
- 前缀和 LeetCode 560.和为K的子数组
- 每日一道leetcode:4. 寻找两个正序数组的中位数
- C 语言的 LeetCode 30 天挑战 第1部分,共10部分
- leetcode每日一题:数组的相对排序