最后一天了，搞了个困难难度的，哭了，看了一早上的题解
题解来自LeetCode的官方题解

题目描述

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

注意: 允许出现重复元素。

insert(val)：向集合中插入元素 val。
remove(val)：当 val 存在时，从集合中移除一个 val。
getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

样例

示例:

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

// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);

// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(1);

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

// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。
collection.getRandom();

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

// getRandom 应有相同概率返回 1 和 2 。
collection.getRandom();

思路

为了使得 O(1)时间内能够随机获取一个元素，我们将每个数值（可以重复）存储在一个列表nums 中。这样，获取随机元素时，只需要随机生成一个列表中的索引，就能够得到一个随机元素。
对于插入元素只需要在引用中和数组中插入元素以及元素对应的下标即可
对于删除元素，用数组中的最后一个元素替代要删除的元素，这样只需要删除最后一个元素即可，但是删除操作比较困难的就是对元素对应的下标的操作，不过如果要删除的元素有多个的话，删除哪一个都可以，对其余操作没有影响，所以每次删除set中存储的第一个下标对应的数据即可。

C++ 代码

class RandomizedCollection {
public:
    unordered_map<int, unordered_set<int>> idx; // 索引（first存储数据，second存储在数组中的下表）
    vector<int> nums; // 存储数据
    /** Initialize your data structure here. */
    RandomizedCollection() {

    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        nums.push_back(val);
        idx[val].insert(nums.size() - 1); // 建立起数据与下标的联系
        // for(auto i : idx)
        // {
        //     cout << i.first << ' ';
        //     for(auto j = i.second.begin(); j != i.second.end(); j ++)
        //         cout << *j << ' ';
        //     cout << endl;
        // }
        // cout << "-----" << endl;
        return idx[val].size() == 1; // 如果val值的set容器中的长度为1就说明以前没有val这个元素，不为1就说明以前有val这个元素。
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if(idx.find(val) == idx.end()) // 遍历map容器查看有没有val这个元素，如果有就返回数据所在的位置，如果没有返回的值就与end返回的值相等
            return false;
        int i = *(idx[val].begin()); // i是val在nums数组中的下标，如果这个值有多个的话，删除哪一个都无关紧要，并不影响其他操作
        nums[i] = nums.back(); // 把要删除的元素替换为数组的最后一个元素
        idx[val].erase(i); // 删除val的i下标
        idx[nums[i]].erase(nums.size() - 1); // 删除最有一个元素的下标
        // for(auto i : idx)
        // {
        //     cout << i.first << ' ';
        //     for(auto j = i.second.begin(); j != i.second.end(); j ++)
        //         cout << *j << ' ';
        //     cout << endl;
        // }
        // cout << "-----" << endl;
        if(i < nums.size() - 1) // 因为第i个数被最后一个数替换，而且最后一个数的下标已经删除，所以如果i的值不等于数组的最后一个，就说明不是删除最后一个元素，要把这个下标更新，更新为要删除的数的下标。
            idx[nums[i]].insert(i);
        if(idx[val].size() == 0) // 如果要删除的数的个数为0（判断下标的个数来判断数组中val的个数）就把这个数据删除
            idx.erase(val);
        // 以上的所有操作均是对下标的变更，nums中的元素并没有变化
        nums.pop_back(); // 删除nums中的元素
        return true;
    }

    /** Get a random element from the collection. */
    int getRandom() {
        return nums[rand() % nums.size()]; // 调用rand()函数生成随机数，模上数组的元素个数，就可以随机访问数组中的元素
    }
};

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