c++ with unoredered_map and vector with clear explain.


  • 0
    E

    Vector is used to GetRandom with O(1). Unoredered_map is used to insert and delete with O(1).
    The key of unoredered_map is val, the value is the index of val in vector. Because O(1) operation for vector is only in the end, so we always process the end of vector.

    class RandomizedSet {
    public:
        /** Initialize your data structure here. */
        RandomizedSet() {}
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            pair<unordered_map<int,int>::iterator,bool>p\
     =hash1.insert(pair<int,int>(val,hash2.size()));
            if(p.second)hash2.push_back(val);
            return p.second;
        }
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            unordered_map<int,int>::iterator it=hash1.find(val);
            if(it!=hash1.end()){
                hash1[hash2.back()]=it->second;
                hash1.erase(it);
                hash2[it->second]=hash2.back();
                hash2.pop_back();
                return 1;
            }else return 0;
        }
        /** Get a random element from the set. */
        int getRandom() {
            if(hash2.empty())return -1;
            int id=rand()%(hash2.size());
            return hash2[id];
        }
    private:
        unordered_map<int,int>hash1;
        vector<int>hash2;
        int n=0;
    };
    
    

Log in to reply
 

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