如何用常数时间插入、删除和获取随机元素
如何用常数时间插入、删除和获取随机元素
作者:Grey
原文地址:
题目链接
LeetCode 380. Insert Delete GetRandom O(1)
主要思路
因为要三个操作都达到O(1)
时间复杂度,所以,我们可以空间换时间,采用两个哈希表来实现
Map<Integer,Integer> indexMap = new HashMap<>();
Map<Integer, Integer> valueMap = new HashMap<>();
这两个哈希表用于存储值和位置关系,比如,初始状态下,两个表都是空的,现在增加一个元素v
,那么我们就把这个元素放到0
号位置上,在哈希表结构中,就做如下操作
indexMap.put(v,0);
valueMap.put(0,v);
接下来来了一个元素x
,我们就把这个元素x
放到1
号位置上,在哈希表的结构中,做如下操作
indexMap.put(x, 1);
valueMap.put(1, x);
这样,
通过indexMap
就可以以时间复杂度O(1)
找到某个元素是否存在,
通过valueMap
就可以以时间复杂度O(1)
找到某个位置的元素是什么。
同时,我们增加一个size
变量来得到当前的元素一共有多少个,在我们调用getRandom()
方法的时候,我们就可以通过
valueMap.get((int) (Math.random() * size));
以O(1)
的时间复杂度,获取到随机位置的一个值。
最后是remove
方法,由于我们可以获取到任何一个位置的值,同时也可以知道任何一个位置所代表的值是什么,我们可以很方便在indexMap
和valueMap
中删除掉对应的记录,
但是,被删除的位置就不是顺序排列的(会有缺口),举个例子,假设生成indexMap
和valueMap
如下
此时,如果要删掉2
位置上的元素,被删除元素后的indexMap
和valueMap
如下
由于产生的缺口,就导致valueMap
在随机取数的时候,如果随机的位置是缺口处,就无法拿到数据,所以,针对remove
操作,我们每次操作完,都要把列表最后一个位置的数,去填补缺口,如上示例中,我们可以将4
号位置的元素去填补空缺,填补后的indexMap
和valueMap
如下
保持表的顺序排列。
注意:在remove
操作中,我们虽然是删除掉某个元素,并且用最后一个位置的元素去替换,但是我们的顺序必须是先取最后一个元素,并且用最后一个元素去覆盖要删除位置的元素,这样操作的目的是,防止删除的元素就是最后一个元素,导致用最后元素填充位置的时候,报空指针异常。
完整代码见
class RandomizedSet {
// 某个val在哪个位置
private Map<Integer, Integer> indexMap;
// 某个位置上的val是什么
private Map<Integer, Integer> valueMap;
private int size;
public RandomizedSet() {
size = 0;
indexMap = new HashMap<>();
valueMap = new HashMap<>();
}
public boolean insert(int val) {
if (!indexMap.containsKey(val)) {
valueMap.put(size, val);
indexMap.put(val, size++);
return true;
}
return false;
}
public boolean remove(int val) {
if (!indexMap.containsKey(val)) {
return false;
}
size--;
int removeIndex = indexMap.get(val);
int lastValue = valueMap.get(size);
valueMap.put(removeIndex, lastValue);
indexMap.put(lastValue, removeIndex);
indexMap.remove(val);
valueMap.remove(size);
return true;
}
public int getRandom() {
return valueMap.get((int) (Math.random() * size));
}
}
更多
相关文章
- 【完全开源】知乎日报UWP版:项目结构说明、关键源代码解释
- UWP开发:APP之间的数据交互(以微信为例)
- 【完全开源】知乎日报UWP版(上篇):界面设计、官方API分析
- 【完全开源】博客园客户端UWP版 带源码、带APP(下篇)
- UWP开发之控件:用WebView做聊天框
- 【完全开源】博客园客户端UWP版(上篇)
- 【完全开源】微信客户端.NET版
- 南通大学2015-2016年1学期《软工》作业点评总结
- 一元、二元函数图像绘制
- 每个人都应该懂点函数式编程
- 百度地图根据经纬度计算瓦片行列号
- 【完全开源】百度地图Web service API C#.NET版,带地图显示控件、导航控件、POI查找控件
- TCP/UDP简易通信框架源码,支持轻松管理多个TCP服务端(客户端)、UDP客户端
- 重中之重:委托与事件
- 可复用代码:组件的来龙去脉
- [史上最全]C#(VB.NET)中位运算符工作过程剖析(译)
- 物以类聚:对象也有生命
- 难免的尴尬:代码依赖
- 博客文章 快速通道
- Some practices to write better C#/.NET code(译)