C++ Solution using a map of vectors to handle duplicates.


  • 2
    F
    class RandomizedCollection {
        vector<pair<int, int>> buffer; // pair.first: the actual value stored; pair.second: the index of the pointer in the idx_map[pair.first]; so idx_map[pair.first][pair.second] is the index of the value in the buffer.
        unordered_map<int, vector<int>> idx_map; // duplicates are stacked into vector<int>
        default_random_engine rng;
    public:
        bool insert(int val) {
            auto is_exist = idx_map.find(val) == idx_map.end() ;
            idx_map[val].push_back(buffer.size()); 
            buffer.emplace_back(val, idx_map[val].size() - 1);
            return is_exist;
        }
        bool remove(int val) {
            if (idx_map.find(val) == idx_map.end())
                return false;
            int idx = idx_map[val].back();
            buffer[idx] = buffer.back();
            idx_map[buffer.back().first][buffer.back().second] = idx;
            idx_map[val].pop_back();
            if (idx_map[val].empty())
                idx_map.erase(val);
            buffer.pop_back();
            return true;
        }
        int getRandom() {
            uniform_int_distribution<int> distribution(0, buffer.size() - 1);
            int idx = distribution(rng);
            return buffer[idx].first;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.