C++ 75ms using unordered_map, List and vector


  • 0
    B

    Using List to complete the insert and remove operations in O(1)

     class RandomizedCollection {
    public:
        typedef list<int> LI;
        typedef pair<int, LI::iterator> PII;
        unordered_map<int, LI>mp;
        vector<PII>v;
        /** Initialize your data structure here. */
        RandomizedCollection() {
            mp.clear();
            v.clear();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            bool flag = false;
            if(!mp.count(val) || mp[val].empty()) flag = true;
            mp[val].push_front(v.size());
            v.push_back(PII(val, mp[val].begin()));
            return flag;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if(!mp.count(val) || mp[val].empty()) return false;
            PII now = v.back();
            v.pop_back();
            mp[now.first].erase(now.second);
            if(now.first != val){
                int n = mp[val].front();
                mp[val].pop_front();
                mp[now.first].push_front(n);
                v[n] = PII(now.first, mp[now.first].begin());   
            }
            return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            int n = rand() % v.size();
            return v[n].first;
        }
    };
    
    /**
     * 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.