C++ right Solution.


  • 0
    C
    1. using struct record to save the value
    2. keep track of the count of valid elements. (validCnt)
    3. maintain the validCnt: n/2 <= validCnt <= n , n = vec.size(). if validCnt < n/2 , rebuild.
    4. insert time complexity O(1)
    5. remove time average O(1)
    6. random expected time complexity O(1) (because of the maintain of validCnt)
    class RandomizedCollection {
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {
            validCnt = 0;
            idx.clear();
            vec.clear();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            auto it = idx.find(val);
            bool exist = it != idx.end();
            
            idx.insert(make_pair(val, vec.size()));
            rec item(val);
            vec.push_back(item);
            validCnt++;
            
            return !exist;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            auto it = idx.find(val);
            if (it == idx.end()) return false;
            //it->first (val)
            //it->second (index)
            
            vec[it->second].valid = false;
            validCnt--;
            idx.erase(it);
            if (validCnt < vec.size() / 2) rebuild();
            
            return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            //vec.size() / 2 <= validCnt <= vec.size()
            while (true) {
                int index = rand() % vec.size();
                if (vec[index].valid == true) return vec[index].val;
            }
            return -1;
        }
        
    private:
        struct rec {
            int val;
            bool valid;
            
            rec (int val) {
                this->val = val;
                this->valid = true;
            }
        };
        int validCnt;
        unordered_multimap<int, int> idx;
        vector <rec> vec;
        
        void rebuild() {
            idx.clear();
            vector <rec> new_vec;
            
            for (auto item: vec) {
                if (!item.valid) continue;
                idx.insert(make_pair(item.val, new_vec.size()));
                new_vec.push_back(item);
            }
            vec = new_vec;
        }
    };
    
    

Log in to reply
 

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