LeetCode#381

LeetCode#381O(1) 时间插入、删除和获取随机元素 - 允许重复

题目链接
题意很简单，让你对一个数组进行插入、删除、返回一个随机数这三种操作，但是要求这三种操作的平均时间复杂度为O（1）。emmm按照题解的指引，为了做到O（1）的时间复杂度，我们需要使用哈希表存储数组中每一个值出现的位置，因为哈希表可以做到近似常数的时间复杂度进行访问元素。而至于删除，我们遵循的原则是将数组中最后一个元素和需要删除的元素进行交换，然后删除最后一个元素，同时更新哈希表的映射。总的来说感觉这个题做了个类似索引的设计，这样就可以快速的访问元素了。
附代码：

class RandomizedCollection
{
public:
    /** Initialize your data structure here. */
    RandomizedCollection()
    {
    }
    unordered_map<int, unordered_set<int>> index;
    vector<int> nums;
    /** 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);
        index[val].insert(nums.size() - 1);
        return index[val].size() == 1;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val)
    {
        if (index[val].size() == 0)//如果这个值的set中不存在元素了，则证明该值元素为空
            return false;
        int i = *(index[val].begin());
        nums[i] = nums[nums.size() - 1];
        index[val].erase(i);
        index[nums[i]].erase(nums.size() - 1);
        if (i < nums.size() - 1)//需要判断操作数的位置，否则可能会造成刚刚删除过索引，然后又加回来的情况。。
        {
            index[nums[i]].insert(i);
        }
        nums.pop_back();
        return true;
    }

    /** Get a random element from the collection. */
    int getRandom()
    {
        if (nums.size() == 0)//判断数组大小，如果为0的话是不能取余的
            return -1;
        return nums[rand() % nums.size()];
    }
};