C++ two solutions


  • 0
    K

    Below are two solutions to the problem which build as an extension of the last problem.

    Solution with map+vector

    #include <stdlib.h> 
    
    class RandomizedCollection {
    private:
        
        unordered_map<int, vector<int>> mmap;
        vector<int> elements;
        
    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) {
            mmap[val].push_back( elements.size() );
            elements.push_back(val);
    
            return mmap[val].size()==1;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            auto bucket = &mmap[val];
            bool found = !bucket->empty();
            
            if (found) {
                int pos = bucket->back(); bucket->pop_back();
                int last = elements.back(); elements.pop_back();
                if (last != val) {
                  mmap[last].back() = pos;
                  elements[pos] = last;
                } 
            }
            
            return found;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            int pos = rand() % elements.size();
            return elements[pos];
        }
    };
    
    

    Solution with multi-map

    
    class RandomizedCollection {
    private:
        unordered_multimap<int, int> map;
        vector<int> elements;
        
    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) {
            int count = map.count(val);
            map.insert(make_pair(val, elements.size()));
            elements.push_back(val);
            
            return !count;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            auto inSet = map.find(val);
            
            if(inSet != map.end()){
                int pos = map.find(val)->second;
                map.erase (map.find(val), ++map.find(val));
                
                int last = elements.back(); elements.pop_back();
                elements[pos] = last;
                
                for(auto findPos = map.find(last); findPos != map.end(); ++findPos){
                    if(findPos->second == elements.size()){
                        map.erase( findPos, std::next(findPos));
                        map.insert( make_pair(last, pos));
                        break;
                    }
                }
            }
            
            return inSet != map.end();
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            int pos = rand() % elements.size();
            return elements[pos];
        }
    };

  • 0

    @kevin36 In your first solution, is "new" good to use here without a destructor?


  • 0
    K

    @haruhiku No its not it create a memory leak, have changed now thanks.


  • 2
    C

    I think the first solution is wrong, though it can be accepted by the OJ.
    For example,["RandomizedCollection","insert","insert","insert","insert","insert","remove","remove","remove","insert","remove"]
    [[],[1],[1],[2],[2],[2],[1],[1],[2],[1],[2]].
    In the last remove, the variable "pos" will be 3 but the size of "elements" is 2.
    However, to my surprise, the OJ pass this case!
    Please correct me if I am wrong


  • 2
    S

    @CtfGo

    Yeah, I've been thinking about this. if you have say:

    [4, 3, 4, 2, 4] and you replace 3 with 4 and set the index of the "last" 4 to 1, that is wrong. If you tried to replace the index of the "last" 4 again, you would be replacing the four at index 1 rather than at index 2.


  • 0
    S

    Got "Runtime Error" on the multi_map solution.

    Here is the accepted multi_map/vector solution:

    class RandomizedCollection {
    private:
        std::vector<int> nums;
        std::unordered_multimap<int, int> pcmap; 
    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) {
            nums.push_back(val);
            int count = pcmap.count(val);
            pcmap.insert(std::make_pair(val, nums.size() - 1));
            return count == 0;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            auto iter = pcmap.find(val);
            if (iter == pcmap.end())
                return false;
            
            int pos = iter->second;
            pcmap.erase(iter, std::next(iter));
            
            int lastVal = nums.back();
            nums[pos] = lastVal;
            
            // Special case in consideration: remove the last inserted value (count: 0->1)
            for (auto iterLast = pcmap.find(lastVal); iterLast != pcmap.end(); iterLast++) {
                if (iterLast->second == nums.size() - 1) {
                    pcmap.erase(iterLast, std::next(iterLast));
                    pcmap.insert(std::make_pair(lastVal, pos));
                    break; // break early to avoid meaningless loops
                }  
            } 
            
            nums.pop_back();  // pop last 
           
            return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            int pos = rand() % nums.size();
            return nums[pos];
        }
    };
    
    /**
     * 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();
     */
    

  • 0
    K

    @storypku That weird it worked yesterday, I have now fixed the problem by just adding a break in the loop.


  • 0

    @CtfGo Thanks, I have added your test case.


  • 0

    @kevin36 This is because new test cases were added recently.


  • 1
    F

    @sircodesalotOfTheRound @CtfGo @kevin36
    I think his first solution is wrong. I had a similar solution:
    https://discuss.leetcode.com/topic/54107/c-solution-using-a-map-of-vectors-to-handle-duplicates
    Then I just browsed different other solutions here. I noticed his solution was similar to mine, but a lot simpler because he always used mmap[last].back() = pos;

    In fact, you have to know where exactly "pos" was pointed from. You can't simply always point your last position of mmap[last] to pos.


Log in to reply
 

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