AC C++ Solution. Unordered_map + Vector


  • 24
    class RandomizedSet {
    public:
        /** Initialize your data structure here. */
        RandomizedSet() {
            
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            if (m.find(val) != m.end()) return false;
            nums.emplace_back(val);
            m[val] = nums.size() - 1;
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if (m.find(val) == m.end()) return false;
            int last = nums.back();
            m[last] = m[val];
            nums[m[val]] = last;
            nums.pop_back();
            m.erase(val);
            return true;
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            return nums[rand() % nums.size()];
        }
    private:
        vector<int> nums;
        unordered_map<int, int> m;
    };
    
    

  • 1
    C

    Here's my getRandom():

    int getRandom() {
            int sz = idr_list.size();
            if (sz == 0)    return -1;
            return idr_list[rand() % sz];
        }
    

    Mod by zero is not defined :)


  • 4

    @chinmay8
    Yes, you are right. Mod by zero is undefined, but I really can't do anything about it. Return any number that is not in the set is wrong, including return -1.


  • 1

    @chinmay8 Actually you can mimic the expected answer.


  • -1
    This post is deleted!

  • 1

    @wtsanshou
    Hi wtsanshou, thank you for your comment.
    This is why I used unordered_map. log(n) is for regular map.

    You can take a look of these:
    http://www.cplusplus.com/reference/map/map/erase/
    http://www.cplusplus.com/reference/unordered_map/unordered_map/erase/
    Time complexities are stated in the documents.


  • 0

    @Ren.W Oh, my mistake. Thank you for your explanation!


  • 0
    X

    Thanks for your method.
    I 'm a freshman in c++, and I'm confused with this problem. What the propose of this problem? I didn't see related knowledge of this problem before, and where can I get more information about this kind of problem?


  • 0
    H

    hello Ren
    I can not understand why this solution is O(1) time, just because I changed the unsorted_map to map and this solution can still passed,and this code like follows is O(log n) time?

    m.find(val) == m.end()

    thanks very much~


  • 0

    Nice solution~~~~~


  • 0

    @Ren-W Could you please explain the logic that you have used in the program? Why exactly do you use a vector and an unordered_map? Thank you!


  • 0

    @BatCoder
    I think using vector to represent the set is to take advantage of vector's [ ] operator, so that we can get the random element.
    Using an unordered_map is to store the elements and their latest indexes.


  • 0
    S
    This post is deleted!

  • 0
    M

    @Ren.W Since you use unordered_map, all insert, remove can be O(1) for unordered_map. Why you use vector again? Only using unordered_map can meet the requirement.


  • 0
    Y

    It's meaningless to use a separate vector to retrieve an element.

    Both std::map and std::set are iterable, which means you can advance the begin() iterator a random number of places and return as a random element from the container.

    Indeed this problem is trivial. Just a wrapper of std::set.


  • 1
    C

    @yuanqili
    Advance the begin() iterator a random number is not O(1). Since iterator can only be moved 1 step at a time, there will be a loop to do that. Correct me if my understanding is not right. Thanks.


  • 0
    X

    My remove function is like this, but I don't know why I get a wrong answer?
    """
    bool remove(int val) {
    if(map.count(val) == 0) return false;
    else{
    if(table.size() == 1){
    map.erase(val);
    table.pop_back();
    return true;
    }
    int index = map[val];
    map.erase(val);
    swap(table[index], table[table.size() - 1]);
    map[table[index]] = index;
    table.pop_back();
    return true;
    }
    }
    """


  • 0

    @Ren-W - The OJ is not accepting my solution since the value for getRandom() is different. However, isn't this how it is expected to behave? Since it is 'random', values would be different.


  • 0
    V

    Can somebody explain why use emplace_back instead of push_back ? is the difference relevant in this case esp with int?


Log in to reply
 

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