20201031
设计一个支持在平均 时间复杂度 O(1) 下, 执行以下操作的数据结构。
注意: 允许出现重复元素。
示例:
// 初始化一个空的集合。
RandomizedCollection collection = new RandomizedCollection();
// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);
// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(1);
// 向集合中插入 2 ,返回 true 。集合现在包含 [1,1,2] 。
collection.insert(2);
// getRandom 应当有 2/3 的概率返回 1 ,1/3 的概率返回 2 。
collection.getRandom();
// 从集合中删除 1 ,返回 true 。集合现在包含 [1,2] 。
collection.remove(1);
// getRandom 应有相同概率返回 1 和 2 。
collection.getRandom();
思路:
题目要求在RandomizedCollection的类中实现:添加insert、删除remove、按比例随机枚举getRandom
因为remove是可以传入元素删除指定元素,可以借助哈希快速查询元素(元素可能重复,则map中存放对应元素数量,当数量为0时删除对应哈希)
抛砖引玉
/**
* Initialize your data structure here.
*/
var RandomizedCollection = function() {
this.map = new Map();
this.list = [];
};
/**
* Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedCollection.prototype.insert = function(val) {
this.list.push(val);
// 记录对应元素在list中是数量
const num = this.map.has(val)?this.map.get(val) + 1: 1
this.map.set(val,num)
// 返回是否为list中第一次出现元素val
return num === 1;
};
/**
* Removes a value from the collection. Returns true if the collection contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedCollection.prototype.remove = function(val) {
// 如果传入的元素在list中不存在直接返回
if (!this.map.has(val)) return false
// 从list中删除指定元素
let index = 0;
while(index < this.list.length){
if(this.list[index] === val){
this.list.splice(index,1)
index = this.list.length
}else{
index++
}
}
// 更细哈希中元素数量
const num = this.map.get(val) -1
if(num === 0) {
// 如果元素数量伪0,删除该哈希
this.map.delete(val)
}else{
this.map.set(val,num)
}
return true;
};
/**
* Get a random element from the collection.
* @return {number}
*/
RandomizedCollection.prototype.getRandom = function() {
// 因为list本身元素可能相同,枚举是只需枚举随机索引
return this.list[Math.floor(Math.random() * this.list.length)];
};
/**
* Your RandomizedCollection object will be instantiated and called as such:
* var obj = new RandomizedCollection()
* var param_1 = obj.insert(val)
* var param_2 = obj.remove(val)
* var param_3 = obj.getRandom()
*/
博客: 前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号:前端小书童