85ms solution from Insert Delete GetRandom O(1) - Duplicates not allowed


  • 1
    I

    the main idea of Insert Delete GetRandom O(1) - Duplicates not allowed is to keep the vector continuous,using the hashmap to keep the position of value. when it comes to Insert Delete GetRandom O(1) - Duplicates allowed,use the hashmap to keep the position of link list's head,when remove the value,update the hashmap and vector to keep vector continuous.

    struct Node {
        int val;
        int next;
    
        Node() : val(0), next(-1) {};
    
        Node(int v, int n) : val(v), next(n) {};
    
    };
    
    class RandomizedCollection {
    public:
        unordered_map<int, int> linkb;
        vector<Node> vec;
    
        /** Initialize your data structure here. */
        RandomizedCollection() {
            srand(time(nullptr));
        }
    
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            bool ret = linkb.find(val) == linkb.end();
            Node t(val, -1);
            if (!ret) t.next = linkb[val];
            linkb[val] = vec.size();
            vec.push_back(t);
            return ret;
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if (linkb.find(val) == linkb.end()) return false;
            int pos = linkb[val];
            if (vec[pos].next == -1) linkb.erase(val);
            else linkb[val] = vec[pos].next;
    
            int p = vec.size() - 1;
            if(p==pos) {
                vec.pop_back();
                return true;
            }
            while (vec[p].next != -1 && vec[p].next > pos)
                p = vec[p].next;
            vec[pos].val = vec.back().val;
            vec[pos].next = vec[p].next;
            vec[p].next = pos;
            linkb[vec.back().val] = vec.back().next;
            vec.pop_back();
            return true;
        }
    
        /** Get a random element from the collection. */
        int getRandom() {
            return vec[rand() % vec.size()].val;
        }
    };
    

Log in to reply
 

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