C++ worst case O(1) time solution


  • 0
    A

    28 / 28 test cases passed
    Status: Accepted
    Runtime: 88 ms

    class RandomizedCollection {
    protected:
        unordered_map<int, unordered_set<uint>> map;
        vector<int> vec;
    public:
        RandomizedCollection() {
        }
    
        bool insert(int val) {
            bool res = !map.count(val);
            map[val].insert(vec.size());
            vec.push_back(val);
            return res;
        }
     
        bool remove(int val) {
            auto it = map.find(val);
            if (it == map.end()) return false;
            uint pos = *it->second.begin(), last = vec.size() - 1;
            if (it->second.size() == 1) map.erase(val);
            else it->second.erase(pos);
            if (pos != last) {
                int tail = vec.back();
                it = map.find(tail);
                it->second.erase(last);
                it->second.insert(pos);
                vec[pos] = tail;
            }
            vec.pop_back();
            return true;
        }
    
        int getRandom() {
            return vec[rand() % vec.size()];
        }
    };
    

Log in to reply
 

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