剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

题目链接

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器 mid

题目描述

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

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

示例 :

输入: inputs = [“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”]
[[], [1], [2], [2], [], [1], [2], []]
输出: [null, true, false, true, 2, true, false, 2]
解释:
RandomizedSet randomSet = new RandomizedSet(); // 初始化一个空的集合
randomSet.insert(1); // 向集合中插入 1 ， 返回 true 表示 1 被成功地插入

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

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

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

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

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

提示：

• $-2^{31}<=val<=2^{31}-1$
• 最多进行 $2\ast 10^5$ 次 insert， remove和 getRandom方法调用
• 当调用 getRandom方法时，集合中至少有一个元素

解法：哈希表 + 随机化

对于一个元素我们可以用一个哈希表 m来记录，这样我们就能实现 $O(1)$的 insert和 remove。

对于题目要求的返回随机元素，且概率相同。我们可以用一个列表 nums存储插入的元素（每次插入都插入到末尾，删除也从末尾删除），这样也是 $O(1)$。

m插入的 key是插入元素的值，value是该元素在 nums中的下标。

insert操作：

remove操作：

getRandom操作：直接返回随机下标 randomIdx = rand() % nums.size()的元素 nums[randomIdx]即可。

时间复杂度： $O(n)$

C++代码：

const int N = 2e5+10;

class RandomizedSet {
public:
    int a[N];
    int idx = -1;
    unordered_map<int,int> m;

    /** Initialize your data structure here. */
    RandomizedSet() {
        srand((unsigned)time(nullptr));
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        //已经存在了 返回false
        if(m.count(val)) return false;
        a[++idx] = val;
        m[val] = idx;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        //如果不存在 返回 false
        if(!m.count(val)) return false;

        int pos = m[val];
        a[pos] = a[idx];
        if(pos != idx) m[a[pos]] = pos;
        idx--;

        m.erase(val);
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        int randomIdx = rand() % (idx + 1);
        return a[randomIdx];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

Python代码：

class RandomizedSet:

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


    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.m:
            return False
        n = len(self.nums)
        self.m[val] = n
        self.nums.append(val)
        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.m:
            return False
        pos = self.m[val]
        self.nums[pos] = self.nums[-1]
        
        self.m[self.nums[pos]] = pos

        self.nums.pop()
        del self.m[val]
        return True        


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



# 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()