C++ 64% two vector, one ud_map, (theoretically faster but in fact slower? )


  • 0
    7

    Variables:
    ELEMENTS: the collection itself
    INDICES[i]: a list of indices of value i in the ELEMENTS
    LOCLIST[i]: the correspondant position of the index of ELEMENT[i] in the INDICES[i]

    Idea:
    While with the two precedent structures, we can solve the first question (duplicate-banned version), here comes a problem when we are trying to delete an element:
    we delete an element from the middle of ELEMENTS, we want to fill this blank with the last element in ELEMENTS, and we need to update at the same time INDICES[last of ELEMENTS].
    To update INDICES[last of ELEMENT], we, with no extra structure will need O(k) where k is maximal duplicated time of all elements. To reduce its complexity, we create a list LOCLIST, which enables us to update the INDICES in constant time. (It's like, we equip the ELEMENTS with pointers which point at their( ELEMENTS[i]) position in the INDICES)

    Unfortunately, I find later that, the time of result using brutal force to update INDICES is even shorter!!!, which makes me a little bit embarrassed after finishing taping all my analysis for this. I can not find a "theoretical" reason for this, I believe that it's just because the scale of the data is not big enough.

    It will be so kind if someone can point out an improvement for my code (or a wrong point in my analysis as well)

    class RandomizedCollection {
        
        vector<int> elements;
        unordered_map<int,vector<int> > indices;
        vector<int> loclist;
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {
            elements=*new vector<int>();
            indices=*new unordered_map<int,vector<int> >();
            loclist=*new vector<int>();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            bool notcontain=indices[val].size()==0;
            loclist.push_back(indices[val].size());
            indices[val].push_back(elements.size());
            elements.push_back(val);
            return notcontain;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            
            if(indices[val].size()==0)return false;
            
            indices[elements.back()][loclist.back()]=indices[val].back();
            elements[indices[val].back()]=elements.back();
            loclist[indices[val].back()]=loclist.back();
            
            indices[val].pop_back();
            elements.pop_back();
            loclist.pop_back();
            return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            return elements[rand()%elements.size()];
        }
    };
    

Log in to reply
 

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