C++ unordered_map + list easy solution ~ 100ms


  • 0
    A
    class RandomizedCollection {
    private:
    	vector<int> nums;
    	unordered_map<int, list<int> > dict;
    	
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {
            srand(time(NULL));
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
    		nums.push_back(val);
            unordered_map<int, list<int> > :: iterator it = dict.find(val);
    		if (it == dict.end()){
    			dict[val] = list<int>(1, nums.size() - 1);
    			return true;
    		}
    		dict[val].emplace_back(nums.size() - 1);
    		return false;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            unordered_map<int, list<int> > :: iterator it = dict.find(val);
    		if (it == dict.end()){
    			return false;
    		}
    		if (dict[val].size() == 0){
    			dict.erase(val);
    			return false;
    		}
    		int pos = dict[val].back();
    		dict[nums.back()].back() = pos;
    		swap(nums[pos], nums[nums.size()-1]);
    		nums.pop_back();
    		dict[val].pop_back();
    		return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            int n = nums.size();
    		return nums[rand() % n];
        }
    	
    	/* fast swap function */
    	void swap(int& a, int& b){
    		a ^= b ^= a ^= b;
    	}
    };
    

Log in to reply
 

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