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;
};
AC C++ Solution. Unordered_map + Vector


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


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


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

@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
andstd::set
are iterable, which means you can advance thebegin()
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;
}
}
"""

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