My AC solution using C++ with unordered_map,unordered_set and vecctor.


  • 0
    K
    class RandomizedCollection {
    public:
        /** Initialize your data structure here. */
        unordered_map<int,unordered_set<int> > hashmap;
        vector<int> nums;
        
        RandomizedCollection() {
            srand((int)time(0));
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            hashmap[val].insert(nums.size());
            nums.push_back(val);
            return hashmap[val].size() == 1;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            auto &it = hashmap[val];
            if(it.empty()) return false;
            if(nums.back() == val){
                nums.pop_back();
                it.erase(nums.size());
            }
            else{
                int n = nums.size();
                int k = it.size();
                
                auto t = it.begin(); 
                nums[*t]= nums[n - 1];
                hashmap[nums[n - 1]].insert(*t);
                hashmap[nums[n - 1]].erase(n - 1);
                
                it.erase(t);
                nums.pop_back();
            }
            return true;
            
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            int i = rand()%nums.size();
            return nums[i];
        }
    };
    
    /**
     * 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.