首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【一天一大 lee】O(1) 时间插入、删除和获取随机元素 - 允许重复 (难度:困难) - Day20201031

【一天一大 lee】O(1) 时间插入、删除和获取随机元素 - 允许重复 (难度:困难) - Day20201031

作者头像
前端小书童
发布2020-11-03 10:19:47
2510
发布2020-11-03 10:19:47
举报
文章被收录于专栏:前端小书童前端小书童

20201031

题目:

设计一个支持在平均 时间复杂度 O(1) 下, 执行以下操作的数据结构。

注意: 允许出现重复元素。

  • insert(val):向集合中插入元素 val。
  • remove(val):当 val 存在时,从集合中移除一个 val。
  • getRandom:从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

示例:

// 初始化一个空的集合。
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

  • Array本身的push、截取或者fliter都可以实现remove、随机枚举可以借助Math.random随机枚举索引完成

因为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 栏目 欢迎关注留言

公众号:前端小书童

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-11-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 前端小书童 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目:
  • 抛砖引玉
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档