# AC C++ Solution. Unordered_map + Vector

• ``````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;
};

``````

• 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 :)

• @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.

• @chinmay8 Actually you can mimic the expected answer.

• This post is deleted!

• @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.

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

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?

• 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~

• Nice solution~~~~~

• @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!

• @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.

• This post is deleted!

• @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.

• 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`.

• @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.

• 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;
}
}
"""

• @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.

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

• @Ren.W Hi, for delete(), I cant understand why we not directly erase val. Can you explain why you copy the value to last element to m[val]. Also, by doing so, how to make sure the average time complexity is O(1).

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