use unordered_multiset solution


  • -1
    F
    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 res = false;
            if(data.find(val) == data.end())
                res = true;
            data.insert(val);
            return res;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            unordered_multiset<int>::iterator it = data.find(val);
            if(it != data.end())
            {
                data.erase(it);
                return true;
            }
            return false;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
           int index = rand()% data.size();
            unordered_multiset<int>::iterator it = data.begin();
            while(index > 0)
            {
                index--;
                it++;
            }
            return *it;
        }
    private:
        unordered_multiset<int> data;
    };
    

    */


  • 0

    @FeiPingWang Your getRandom() is not O(1)... :(


  • 0
    F

    You are right, i make a change to use vector and hashmap, thank you!


Log in to reply
 

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