c++ solution


  • 0
    P

    '''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) {
        vec.push_back(val);
        map[val].insert(vec.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.find(val) == map.end() || map[val].size()==0)
            return false;
        if(vec.back()==val){
            vec.pop_back();
            map[val].erase(map[val].find(vec.size()));
        }
        else{
            int index = *map[val].begin();
            map[val].erase(map[val].begin());
            swap(vec[index], vec[vec.size()-1]);
            vec.pop_back();
            map[vec[index]].erase(map[vec[index]].find(vec.size()));
            map[vec[index]].insert(index);
        }
        return true;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        return vec[rand()%vec.size()];
    }
    

    private:
    unordered_map<int, unordered_multiset<int>> map;
    vector<int> vec;
    };
    /**

    • 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();
      */'''

Log in to reply
 

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