【leetcode】【剑指offer Ⅱ】030. 插入、删除和随机访问都是 O(1) 的容器

问题描述：

• 设计一个支持在平均时间复杂度 O(1) 下，执行以下操作的数据结构：
  • insert(val)：当元素 val 不存在时返回 true，并向集合中插入该项，否则返回 false。
  • remove(val)：当元素 val 存在时返回 true，并从集合中移除该项，否则返回 false。
  • getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

核心思路：

• 该题比想象中要简单很多，变长数组可以在 O(1) 的时间内完成随机访问元素操作，哈希表可以在 O(1) 的时间内完成插入和删除操作，所以该题只需要将变长数组结合哈希表进行存储即可。
• 变长数组存储数值，哈希表用来保存值与数组中索引的映射：
  • insert(val) 操作：首先需要在哈希表中查找是否已经存在，如果存在则返回 false，如果不存在则直接存入数组中，并将值与对应的索引存储在哈希表中。
  • delete(val) 操作：首先同样需要在哈希表中查找是否已经存在，如果不存在则返回 false，如果存在则要进行相应的删除。
    • 有一种直接的办法，可以只擦除哈希表中对应的键值对，而不更新边长数组，因为查找操作只影响哈希表，且变长数组无法做到在 O(1) 时间内删除元素；但这种方法不可取，因为变长数组可能会一直增大。
    • 所以在删除哈希表对应键值对之前，需要首先把该值 val 与数组中最后一个数 num 进行交换，如此 num 的索引就变成了 val 的索引，再对 val 对应的键值对删除即可，同时变长数组可以弹出最后一个元素，使得数组大小得到控制。
  • getRandom 操作：O(1) 的随机访问操作说明容器可以通过索引访问，所以这里也说明了要实现该容器需要数组来存放数据。

代码实现：

class RandomizedSet
{
private:
    vector<int> vec;
    unordered_map<int, int> mapped;
public:
    /** Initialize your data structure here. */
    RandomizedSet() {}
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val)
    {
        if(mapped.count(val)) return false;
        mapped[val] = vec.size();
        vec.push_back(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val)
    {
        if(!mapped.count(val)) return false;
        int idx = mapped[val];
        vec[idx] = vec[vec.size()-1];
        mapped[vec[idx]] = idx;
        mapped.erase(val);
        vec.pop_back();
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom()
    {
        return vec[rand()%vec.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36