变长数组 + 哈希表解决“O(1) 时间插入、删除和获取随机元素”问题
十一、O(1) 时间插入、删除和获取随机元素
11.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 方法时,数据结构中 至少存在一个 元素。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/insert-delete-getrandom-o1
11.2、解题思路
-
先定义一个List存放values和map存放(val,index);
-
在RandomizedSet中将定义的List和map初始化;
-
在insert中,先判断map中是否存在val,存在则为false,不存在则将val添加到values并更新map;
-
在remove中,先判断map中是否存在val,不存在则为false,存在则搜索出val在map中的index,再将需要删除的元素移到末尾,然后移除values最后一位元素,最后将map更新并删除即可;
-
在getRandom中,先引入random库函数,最后随机取出一个数的index并返回即可。
使用Map的containsKey()方法来检测数据(value)是否存在,如果key存在,则表明已经获取过一次数据,那么直接返回该 Key 在Map中的值,不管是否为nul都直接返回;如果key不存在,则去生成或者获取数据,并放入到Map中,并返回该数据。
11.3、算法
class RandomizedSet {
//array存放的是所有的values
List<Integer> values;
//map里面存放的是val和values存放的下标index之间的关系(val,index)
Map<Integer,Integer> map;
//初始化
public RandomizedSet() {
values = new ArrayList();
map = new HashMap();
}
//插入操作
public boolean insert(int val) {
//如果map中已经存在val,返回false
if(map.containsKey(val)){
return false;
}
//先将val添加到values
values.add(val);
//再更新map
map.put(val,values.size()-1);
return true;
}
//删除操作
public boolean remove(int val) {
//如果map中不包含val,返回false
if(!map.containsKey(val)){
return false;
}
//搜索val在map中的index
int index = map.get(val);
//将需要删除的元素移到末尾再删除,否则就会出现数据搬移
int last = values.get(values.size()-1);
values.set(index,last);
//移除values最后一位元素
values.remove(values.size()-1);
//在map中更新
map.put(last,index);
//在map中删除
map.remove(val);
return true;
}
public int getRandom() {
//先引入random的库函数
Random random = new Random();
//最后随机取出一个数的index并返回即可
return values.get(random.nextInt(values.size()));
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
参考视频:B站up主Ronan0
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgafjgh
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13