C++ easy solution


  • 0
    M

    I was inspired by some others' solution, the main problem for the solution is that when we try to swap the element to the end, the index of the back element may not be the the last element in the index table.

    One way to resolve this is use priority queue instead of vector, this container will always give the biggest element, so index of last element should be popped after we swap while the constant complexity still holds. The idea is the same.

    unordered_map<int,priority_queue<int>> m_index;
        vector<int> nums;
        
        RandomizedCollection() {
           
        }
       
        bool insert(int val) {
            nums.push_back(val);
            m_index[val].push(nums.size()-1);
            return m_index[val].size()==1;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if(m_index[val].empty())
            return 0;
            int index=m_index[val].top();
            if(index==nums.size()-1){
                nums.pop_back();
                m_index[val].pop();
            }
            else{
            nums[index]=nums.back();
            m_index[nums.back()].push(index);
            m_index[nums.back()].pop();
             m_index[val].pop();
            nums.pop_back();
            }
            return 1;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            if(nums.empty())
            return -1;
            return nums[rand()%nums.size()];
        }
    

  • 0
    Z

    The problem requires O(1) operation time, if we use a priority_queue, the time complexity is O(logk) when pushing element into it, in which k is the duplicated elements number.


Log in to reply
 

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