Skip to content

leetcode380：常数时间插入、删除和获取随机元素 #48

Open
Open
leetcode380：常数时间插入、删除和获取随机元素#48
Labels
LeetCode字节

Description

@sisterAn
sisterAn
opened on May 24, 2020

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

  • insert(val) ：当元素 val 不存在时，向集合中插入该项。
  • remove(val) ：元素 val 存在时，从集合中移除该项。
  • getRandom ：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

附赠leetcode地址：leetcode

Activity

  1. sisterAn
    added
    LeetCode
    字节
    on May 24, 2020

  2. plane-hjh commented on May 25, 2020

    @plane-hjh
    plane-hjh
    on May 25, 2020
    let RandomizedSet = function() {
    this.list = []
    this.map = {}
};

RandomizedSet.prototype.insert = function(val) {
    if(this.map[val]) return false

    this.list.push(val)
    this.map[val] = this.list.length
    return true
};

RandomizedSet.prototype.remove = function(val) {
    if(!this.map[val]) return false

    const final = this.list[this.list.length-1]

    // 下面这块主要是把要数组的尾值赋给对应的val值的位置，之后把数组最后的值踢出去即可
    const index = this.map[val]
    // 这里的index-1即我们拿到的index不是数组的下标，还需要减1。
    this.list[index-1] = final
    this.map[final] = index

    delete this.map[val]
    this.list.pop()

    return true
};

RandomizedSet.prototype.getRandom = function() {
    const index = Math.floor(Math.random() * this.list.length)
    return this.list[index]
};

  3. Loading-m commented on May 25, 2020

    @Loading-m
    Loading-m
    on May 25, 2020
    /**
 * Initialize your data structure here.
 */
var RandomizedCollection = function() {
    this.list = []
    this.map = {}
};

/**
 * 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)

    if(!this.map[val] || this.map[val].length == 0) {
        // val 在map中的下标集合，相同的val可能有多个，所以用数组来存储下标值
        this.map[val] = [this.list.length-1]
        return true
    } else {
        this.map[val].unshift(this.list.length-1)
        return false
    }
};

/**
 * 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) {
    if(!this.map[val] || this.map[val].length == 0) return false

    const index = this.map[val].shift()
    const final = this.list[this.list.length-1]

    if(final !== val) {
        this.list[index] = final
        this.map[final][0] = index
        this.map[final].sort((a,b) => b-a)
    }

    this.list.pop()
    return true
};

/**
 * Get a random element from the collection.
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function() {
    const index = Math.floor(Math.random() * this.list.length)
    return this.list[index]
};

    这个getRandom不是要概率相等吗 这个概率为什么是相等的

  4. 7777sea commented on May 25, 2020

    @7777sea
    7777sea
    on May 25, 2020
    /**
 * Initialize your data structure here.
 */
var RandomizedSet = function() {
    this.list = [];
    this.map = {};
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if(!this.map[val]){
        this.list.push(val)
        this.map[val] = this.list.length
        return true
    }else{
        return false
    }
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if(this.map[val]){
        this.list = this.list.filter(item => item != val)
        delete this.map[val]
        return true
    }else{
        return false
    }  
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    function randomFrom(lowerValue,upperValue){
        return Math.floor(Math.random() * (upperValue - lowerValue) + lowerValue);
    }

    return this.list[randomFrom(0, this.list.length)]
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

  5. luweiCN commented on May 25, 2020

    @luweiCN
    luweiCN
    on May 25, 2020

    自己没想出来，看了题解的提示想到用Map和数组结合的方式。不得不说remove的操作因为惯性思维不太容易想到

    /**
 * Initialize your data structure here.
 */
var RandomizedSet = function () {
  //表示数组中的对应的值的下标是多少
  //然后删除的时候就可以根据val找到数组里面的下标 然后在数组中进行删除
  this.map = new Map();

  //存放值
  this.values = [];
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
  //如果已经有这个值了就返回false
  if (this.map.has(val)) {
    return false;
  } else {
    //在表中记录插入的值在数组中的下标
    this.map.set(val, this.values.length);
    //在数组中添加这个值
    this.values.push(val);
    return true;
  }
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
  if (this.map.has(val)) {
    // 找到要删除的值的下标
    const deleteIndex = this.map.get(val);
    // 得到最后一个元素
    const lastVal = this.values.pop();
    // 用最后一个数代替要删除的值
    this.values[deleteIndex] = lastVal;
    // 更新本来是最后一个元素在map中记录的下标
    this.map.set(lastVal, deleteIndex);

    // 在map中删除
    this.map.delete(val);

    return true;
  } else {
    //如果没有这个值就返回false
    return false;
  }
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
  let size = this.values.length;
  //返回一个0到values的长度之间的随机数
  let random = Math.floor(Math.random() * size);
  //以随机数为下标返回
  return this.values[random];
};

  6. luweiCN commented on May 25, 2020

    @luweiCN
    luweiCN
    on May 25, 2020
    let RandomizedSet = function() {
    this.list = []
    this.map = {}
};

RandomizedSet.prototype.insert = function(val) {
    this.list.push(val)

    if(!this.map[val] || this.map[val].length == 0) {
        // val 在map中的下标集合，相同的val可能有多个，所以用数组来存储下标值
        this.map[val] = [this.list.length-1]
        return true
    } else {
        this.map[val].unshift(this.list.length-1)
        return false
    }
};

RandomizedSet.prototype.remove = function(val) {
    if(!this.map[val] || this.map[val].length == 0) return false

    const index = this.map[val].shift()
    const final = this.list[this.list.length-1]

    if(final !== val) {
        this.list[index] = final
        this.map[final][0] = index
        this.map[final].sort((a,b) => b-a)
    }

    this.list.pop()
    return true
};

RandomizedSet.prototype.getRandom = function() {
    const index = Math.floor(Math.random() * this.list.length)
    return this.list[index]
};

    insert有问题吧，insert 的时候如果有已经存在，按照题目要求返回false，为什么要用数组把它们下标都存下来

  7. plane-hjh commented on May 25, 2020

    @plane-hjh
    plane-hjh
    on May 25, 2020
    let RandomizedSet = function() {
    this.list = []
    this.map = {}
};

RandomizedSet.prototype.insert = function(val) {
    this.list.push(val)

    if(!this.map[val] || this.map[val].length == 0) {
        // val 在map中的下标集合，相同的val可能有多个，所以用数组来存储下标值
        this.map[val] = [this.list.length-1]
        return true
    } else {
        this.map[val].unshift(this.list.length-1)
        return false
    }
};

RandomizedSet.prototype.remove = function(val) {
    if(!this.map[val] || this.map[val].length == 0) return false

    const index = this.map[val].shift()
    const final = this.list[this.list.length-1]

    if(final !== val) {
        this.list[index] = final
        this.map[final][0] = index
        this.map[final].sort((a,b) => b-a)
    }

    this.list.pop()
    return true
};

RandomizedSet.prototype.getRandom = function() {
    const index = Math.floor(Math.random() * this.list.length)
    return this.list[index]
};

    insert有问题吧，insert 的时候如果有已经存在，按照题目要求返回false，为什么要用数组把它们下标都存下来

    不好意思，没看清，已改，谢谢指出 @luweiCN

  8. sisterAn commented on May 25, 2020

    @sisterAn
    sisterAn
    on May 25, 2020
    OwnerAuthor

    解答一：Map+数组

    const RandomizedSet = function() {
    this.map = new Map()
    this.values = []
};

RandomizedSet.prototype.insert = function(val) {
    // 存在
    if(this.map.has(val)) {
        return false
    }
    // 不存在
    this.map.set(val, this.values.length)
    this.values.push(val)
    return true
};

RandomizedSet.prototype.remove = function(val) {
    // 不存在
    if(!this.map.has(val)) {
        return false
    } 
    
    const index = this.map.get(val)
    // 存在且为最后一个元素
    if(index === this.values.length - 1) {
        this.values.pop()
        this.map.delete(val)
    } else { // 存在不为最后一个元素
        const lastValue = this.values.pop()
        this.values[index] = lastValue
        this.map.set(lastValue, index)
        this.map.delete(val)
    }
    return true
};

RandomizedSet.prototype.getRandom = function() {
    const length = this.values.length
    const random = Math.floor(Math.random() * length)
    return this.values[random];
};

    解答二：也可以使用Set

    const RandomizedSet = function() {
    this.set = new Set()
}
RandomizedSet.prototype.insert = function(val) {
    if (this.set.has(val)) {
        return false
    }
    this.set.add(val)
    return true
}
RandomizedSet.prototype.remove = function(val) {
    if (!this.set.has(val)) {
        return false
    }
    this.set.delete(val)
    return true
}
RandomizedSet.prototype.getRandom = function() {
    const random = parseInt(Math.random()*(this.set.size))
    return [...this.set][random]
}

    leetcode

  9. 13001920223 commented on May 26, 2020

    @13001920223
    13001920223
    on May 26, 2020
    var RandomizedSet = function() {
    this.hashMap = new Map();
    this.arr = [];
}

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if (this.hashMap.has(val)) {
        return false
    } else {
        this.hashMap.set(val, this.arr.length);
        this.arr.push(val);
        return true
    }
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    var delIndex = this.hashMap.get(val);
    if (delIndex === undefined) {
        return false;
    } else {
        var lastNum = this.arr[this.arr.length - 1];
        this.arr[delIndex] = lastNum;
        this.hashMap.set(lastNum, delIndex);
        this.arr.pop();
        return this.hashMap.delete(val);
    }
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    var random = Math.floor(Math.random() * this.arr.length);
    return this.arr[random];
};

  10. guanping1210 commented on May 26, 2020

    @guanping1210
    guanping1210
    on May 26, 2020
      const RandomizedSet = function() {
        this.list = []
        this.map = new Map()
    }

    RandomizedSet.prototype.insert = function(val) {
        // 有val，返回false
        if(this.map[val]) return false

        // val不存在，则存储起来，并且记录val的下标位置
        this.list.push(val)
        this.map[val] = this.list.length - 1
        return true
    }

    RandomizedSet.prototype.remove = function(val) {
        // 不存在val，返回false
        if(!this.map[val]) return false

        // val存在，则在map和list中删除val
        this.list.splice(this.map[val], 1)
        delete this.map[val]
        return true
    }

    // 返回list中的任意随机数
    RandomizedSet.prototype.getRandom = function() {
        return this.list[Math.floor(Math.random() * (this.list.length))]
    }

  11. AnranS commented on Nov 14, 2020

    @AnranS
    AnranS
    on Nov 14, 2020
    /**
 * Initialize your data structure here.
 */
var RandomizedSet = function () {
    this.hash = {};
    this.arr = [];
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
    // 如果存在返回false
    if (this.hash[val] !== undefined) {
        return false;
    } else {
        // 如果不存在hash表中，将其加入arr中，并数之hash以val为键的值为当前index
        this.arr.push(val);
        this.hash[val] = this.arr.length - 1; // 其实就是当前值在数组中的index
        return true;
    }
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
    // 存在才删除
    if (this.hash[val] !== undefined) {
        // 交换当前值与数组末尾元素
        [this.arr[this.hash[val]], this.arr[this.arr.length - 1]] = [this.arr[this.arr.length - 1], this.arr[this.hash[val]]];
        // 更改末尾元素的index
        this.hash[this.arr[this.hash[val]]] = this.hash[val];
        // 清除末尾元素
        this.arr.pop();
        // 删除hash表中的值
        delete this.hash[val];
        return true;
    } else {
        return false;
    }
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
    return this.arr[Math.random()*(this.arr.length) | 0];
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

  12. azl397985856 commented on Mar 3, 2021

    @azl397985856
    azl397985856
    on Mar 3, 2021

    题目地址（380. 常数时间插入、删除和获取随机元素）

    https://leetcode-cn.com/problems/insert-delete-getrandom-o1/description/

    题目描述

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

insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

    思路

    这是一个设计题。这道题的核心就是考察基本数据结构和算法的操作以及复杂度。

    我们来回顾一下基础知识：

    • 数组支持随机访问，其按照索引查询的时间复杂度为$O(1)$,按值查询的时间复杂度为$O(N)$， 而插入和删除的时间复杂度为$O(N)$。
    • 链表不支持随机访问，其查询的时间复杂度为$O(N)$,但是对于插入和删除的复杂度为$O(1)$（不考虑找到选要处理的节点花费的时间）。
    • 对于哈希表，正常情况下其查询复杂度平均为$O(N)$，插入和删除的复杂度为$O(1)$。

    由于题目要求 getRandom 返回要随机并且要在$O(1)$复杂度内，那么如果单纯使用链表或者哈希表肯定是不行的。

    而又由于对于插入和删除也需要复杂度为$O(1)$，因此单纯使用数组也是不行的，因此考虑多种使用数据结构来实现。

    实际上 LeetCode 设计题，几乎没有单纯一个数据结构搞定的，基本都需要多种数据结构结合，这个时候需要你对各种数据结构以及其基本算法的复杂度有着清晰的认知。

    对于 getRandom 用数组很简单。对于判断是否已经有了存在的元素，我们使用哈希表也很容易做到。因此我们可以将数组随机访问，以及哈希表$O(1)$按检索值的特性结合起来，即同时使用这两种数据结构。

    对于删除和插入，我们需要一些技巧。

    对于插入：

    • 我们直接往 append，并将其插入哈希表即可。
    • 对于删除，我们需要做到 O(1)。删除哈希表很明显可以，但是对于数组，平均时间复杂度为 O(1)。

    因此如何应付删除的这种性能开销呢？ 我们知道对于数据删除，我们的时间复杂度来源于

    1. 查找到要删除的元素
    2. 以及重新排列被删除元素后面的元素。

    对于 1，我们可以通过哈希表来实现。 key 是插入的数字，value 是数组对应的索引。删除的时候我们根据 key 反查出索引就可以快速找到。

    题目说明了不会存在重复元素，所以我们可以这么做。思考一下，如果没有这个限制会怎么样？

    对于 2，我们可以通过和数组最后一项进行交换的方式来实现，这样就避免了数据移动。同时数组其他项的索引仍然保持不变，非常好！

    相应地，我们插入的时候，需要维护哈希表

    图解：

    以依次【1，2，3，4】之后为初始状态，那么此时状态是这样的：

    而当要插入一个新的 5 的时候， 我们只需要分别向数组末尾和哈希表中插入这条记录即可。

    而删除的时候稍微有一点复杂：

    关键点解析

    • 数组
    • 哈希表
    • 数组 + 哈希表
    • 基本算法时间复杂度分析

    代码

    from random import random


class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = dict()
        self.arr = []
        self.n = 0

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val in self.data:
            return False
        self.data[val] = self.n
        self.arr.append(val)
        self.n += 1

        return True

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val not in self.data:
            return False
        i = self.data[val]
        # 更新data
        self.data[self.arr[-1]] = i
        self.data.pop(val)
        # 更新arr
        self.arr[i] = self.arr[-1]
        # 删除最后一项
        self.arr.pop()
        self.n -= 1

        return True

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """

        return self.arr[int(random() * self.n)]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

    复杂度分析

    • 时间复杂度：$O(1)$
    • 空间复杂度：$O(1)$

    更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。

    大家也可以关注我的公众号《力扣加加》获取更多更新鲜的 LeetCode 题解

  13. JohnApache commented on Apr 30, 2021

    @JohnApache
    JohnApache
    on Apr 30, 2021

    为什么都用list + map, list 存储数据方便，但是删除数据就不算很优雅了啊，我直接用了 两个 map 实现这个效果

    class RandomizedSet {

    private mapValueToIndex: Record<number, number> = {};
    private mapIndexToValue: Record<number, number> = {};
    public length: number = 0;

    insert (data: number) {
        if (this.mapValueToIndex[data] !== undefined) return false;
        this.mapValueToIndex[data] = this.length;
        this.mapIndexToValue[this.length] = data;
        this.length++;
        return true;
    }

    remove (data: number) {
        const removeDataIndex = this.mapValueToIndex[data];
        if (removeDataIndex === undefined) return false;
        delete this.mapValueToIndex[data];
        delete this.mapIndexToValue[removeDataIndex];
        this.length--;
        return true;
    }

    getRandom () {
        const randomIndex = Math.floor(this.length * Math.random());
        return this.mapIndexToValue[randomIndex];
    }

}

const randomSet = new RandomizedSet();
console.log(randomSet.insert(1));
console.log(randomSet.remove(2));
console.log(randomSet.insert(2));
console.log(randomSet.getRandom());
console.log(randomSet.remove(1));
console.log(randomSet.insert(2));
console.log(randomSet);

// 输出
// true
// false
// true
// 1 或者 2
// true
// false
// RandomizedSet {
//   mapValueToIndex: { '2': 1 },
//   mapIndexToValue: { '1': 2 },
//   length: 1
// }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    LeetCode字节

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions