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

  • 0

    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]

    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;
        /** 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;
            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;
            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.