c++ 62ms with promoted hash table


  • 0
    E

    Refer to the problem Insert Delete GetRandom O(1), my former algorithm is this:c++ with unoredered_map and vector with clear explain..
    For this problem,multimap is not suitable for "delete",so I use map<int,set<int> >.

    class RandomizedCollection {
    private:
        unordered_map<int,unordered_set<int> >hash1;
        vector<int>hash2;
    public:
        RandomizedCollection() {}
        bool insert(int val) {
            auto it=hash1.find(val);
            if(it!=hash1.end()){
                it->second.insert(hash2.size());
                hash2.push_back(val);
                return 0;
            }else{
                hash1.insert(pair<int,unordered_set<int> >(val,unordered_set<int>{hash2.size()}));
                hash2.push_back(val);
                return 1;
            }
        }
        bool remove(int val) {
            auto it=hash1.find(val);
            if(it!=hash1.end()){
                hash1[hash2.back()].erase(hash2.size()-1);
                if(val!=hash2.back()){
                    int pos=*hash1[val].begin();
                    hash1[hash2.back()].insert(pos);
                    hash1[val].erase(hash1[val].begin());
                    hash2[pos]=hash2.back();
                }
                if(hash1[val].empty())hash1.erase(it);
                hash2.pop_back();
                return 1;
            }else return 0;
        }
        int getRandom() {
            if(hash2.empty())return -1;
            return hash2[rand()%(hash2.size())];
        }
    };
    

Log in to reply
 

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