C++ Solution using unordered_map and priority_queue


  • 0
    G
    class RandomizedCollection {
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {}
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            m[val].push(nums.size());
            nums.push_back(val);
    	return m[val].size() == 1;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if (m[val].empty()) return false;
            int idx = m[val].top();
    	m[val].pop();
    	if (nums.size() - 1 != idx) {
    	    int t = nums.back();
    	    nums[idx] = t;
    	    m[t].pop();
    	    m[t].push(idx);
    	}
    	nums.pop_back();
            return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            return nums[rand() % nums.size()];
        }
    private:
        vector<int> nums;
        unordered_map<int, priority_queue<int>> m;
    };
    

  • 0
    M

    The index removed by m[t].pop() might be not the same as the one of nums.back()


  • 0
    G

    @Mike2016
    I think they are same because the priority_queue guarantees the biggest index will be popped which should be the last element of the array.


  • 0

    I believe your solution is good enough. Since priority_queue insertion complexity is up to logN, I'm afraid that is not perfect for this question...


Log in to reply
 

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