381. Insert Delete GetRandom O(1) Duplicates allowed - cocoder39/coco39_LC GitHub Wiki

int back = nums.back(); 
        auto it2 = map.find(back);

class RandomizedCollection {
public:
    /** 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) {
        bool exist = map.find(val) == map.end();
        nums.push_back(val);
        map.insert({val, nums.size() - 1});
        return exist;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        auto it1 = map.find(val);
        if (it1 == map.end()) {
            return false;
        }
        int back = nums.back(); 
        auto it2 = map.find(back); //iterator may point to a different element but with same value as back
        swap(nums[it1->second], nums[it2->second]);
        nums.resize(nums.size() - 1);
        it2->second = it1->second;
        map.erase(it1); 
        return true;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        if (nums.empty()) 
            return 0;
        return nums[rand() % nums.size()];
    }
private:
    vector<int> nums;
    unordered_multimap<int, int> map;
};

class RandomizedCollection {
public:
    /** 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);
        map[val].insert(nums.size() - 1);
        return map[val].size() == 1;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if (map[val].empty()) {
            return false;
        }
        
        int idx = *(map[val].begin());
        map[val].erase(map[val].begin());
        
        int last = nums.back();
        nums[idx] = last;
        map[last].insert(idx);
        map[last].erase(nums.size() - 1);
        nums.pop_back();
        return true;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        if (nums.empty()) 
            return 0;
        return nums[rand() % nums.size()];
    }
private:
    vector<int> nums;
    unordered_map<int, unordered_set<int>> map;
};