c++ with unordered_map


  • 0
    H

    /** Initialize your data structure here. */
    unordered_map<int,int> map;
    int size;
    RandomizedCollection() {
    size=0;
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        size++;
        if(map.count(val)>0)
        {
            map[val]++;
            return false;
        }else
        {
            map[val]=1;
            return true;
        }
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if(map.count(val)>0)
        {
            if(map[val]==1)map.erase(val);
            else map[val]--;
            size--;
            return true;
        }
        return false;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        int chose=rand() % size + 1;
        unordered_map<int,int>::iterator it;
        for(it=map.begin();it!=map.end();++it)
        {
            if(chose<=it->second)return it->first;
            else 
            {
                chose-=it->second;
            }
        }
        return it->first;
    }
    

    };


  • 0
    P

    I think the getRandom() part is O(n) on average, not O(1).


Log in to reply
 

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