# C++ right Solution.

1. using `struct record` to save the value
2. keep track of the count of valid elements. (`validCnt`)
3. maintain the validCnt: `n/2 <= validCnt <= n` , n = vec.size(). if validCnt < n/2 , `rebuild`.
4. insert time complexity O(1)
5. remove time average O(1)
6. random expected time complexity O(1) (because of the maintain of `validCnt`)
``````class RandomizedCollection {
public:
/** Initialize your data structure here. */
RandomizedCollection() {
validCnt = 0;
idx.clear();
vec.clear();
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool insert(int val) {
auto it = idx.find(val);
bool exist = it != idx.end();

idx.insert(make_pair(val, vec.size()));
rec item(val);
vec.push_back(item);
validCnt++;

return !exist;
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
auto it = idx.find(val);
if (it == idx.end()) return false;
//it->first (val)
//it->second (index)

vec[it->second].valid = false;
validCnt--;
idx.erase(it);
if (validCnt < vec.size() / 2) rebuild();

return true;
}

/** Get a random element from the collection. */
int getRandom() {
//vec.size() / 2 <= validCnt <= vec.size()
while (true) {
int index = rand() % vec.size();
if (vec[index].valid == true) return vec[index].val;
}
return -1;
}

private:
struct rec {
int val;
bool valid;

rec (int val) {
this->val = val;
this->valid = true;
}
};
int validCnt;
unordered_multimap<int, int> idx;
vector <rec> vec;

void rebuild() {
idx.clear();
vector <rec> new_vec;

for (auto item: vec) {
if (!item.valid) continue;
idx.insert(make_pair(item.val, new_vec.size()));
new_vec.push_back(item);
}
vec = new_vec;
}
};

``````

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