设计容器

发表于

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

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
class RandomizedSet {
public:
    vector<int> v;
    map<int, int> m;
    bool insert(int val) {
        if (m.find(val) != m.end()) {
            return false;
        }
        v.push_back(val);
        m[val] = v.size() - 1;
        return true;
    }
        bool remove(int val) {
        if (m.find(val) == m.end()) {
            return false;
        } else {
            int i = m[val];                                //
            int last = v[v.size()-1];
            m.erase(val);
            v[i] = last;
            v.pop_back();
            if (v.size() != i)                       //
                m[last] = i;
        }
        return true;
    }
    int getRandom() {
        int n = v.size();
        return v[rand()%n];         
    }
};