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

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

class RandomizedCollection {
public:

    unordered_map>hash;
    vector nums;
    // 380基础上 哈希套哈希
    RandomizedCollection() {

    }
    
    bool insert(int val) {
        bool res = hash[val].empty();
        
        nums.push_back(val);
        hash[val].insert(nums.size() - 1);
        
        return res;
    }
    
    bool remove(int val) {
        if(!hash[val].size()) return false;
        int x = val, y = nums.back();
        int px = *(hash[x].begin()), py = nums.size() - 1;
        swap(nums[px], nums[py]);
        nums.pop_back();
        hash[x].erase(px); hash[x].insert(py);
        hash[y].erase(py); hash[y].insert(px);
        hash[x].erase(py);
        return true;
    }
    
    int getRandom() {
        return nums[rand() % nums.size()];
    }
};