Insert Delete GetRandom O(1) – Duplicates allowed

Insert Delete GetRandom O(1) – Duplicates allowed

描述

设计一个数据结构, 存在三种操作, 写入, 删除, 随机获取一个元素, 并且满足:

  1. 复杂度为\(O(1)\)
  2. 允许重复元素
  3. 随机获取元素与元素的数量成正比, 如存在(1, 1, 2)三个元素, 则随机获取时获得1的概率为获得2的概率的两倍

分析

先说一下结论, 我最后完成的能过的答案大致满足复杂度的条件(不是完全满足)

写入, 删除复杂度的数据结构, 哈希表就能满足, 但是哈希表不能随机获取元素, 数组可以随机获取元素, 所以我们可以将数据存为两份, 一份在哈希表里, 通过k存取, 一份在数组里, 可以根据随机获取

使用额外的另一个数组多次存储元素, 以应对允许重复元素的情况

删除哈希表的元素比较简单, 直接删除即可, 在删除数组元素时, 实时调整数组长度复杂度较高, 我们直接将对应位置为False表示元素已删除

在随机获取元素时, 随机在数组中获取, 如获取的元素为False, 重试(如删除的元素过多, 重试的次数过长, 会导致实际复杂度提高)

具体来说, 大体过程如下:

init:
    m = {}
    n = []
insert 1:
    m = {1:[0]}
    n = [1]
insert 1:
    m = {1: [0, 1]}
    n = [1, 1]
inser 2:
    m = {1: [0, 1], 2: [2]}
    n = [1, 1, 2]
remove 1:
    m = {1: [0], 2: [2]}
    n = [1, False, 2]

一个能过ac的代码如下

答案

import random
class RandomizedCollection(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.m = {}
        self.n = []


    def insert(self, val):
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.m:
            self.m[val] = [len(self.n)]
            self.n.append(val)
            return True
        self.m[val].append(len(self.n))
        self.n.append(val)
        return False


    def remove(self, val):
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.m:
            index = self.m[val].pop()
            if len(self.m[val]) == 0:
                del(self.m[val])
            self.n[index] = False
            return True
        return False


    def getRandom(self):
        """
        Get a random element from the collection.
        :rtype: int
        """
        if len(self.m) == 0:
            return None
        while True:
            r = random.randint(0, len(self.n) - 1)
            if self.n[r] is not False:
                return self.n[r]
打赏