I was inspired by some others' solution, the main problem for the solution is that when we try to swap the element to the end, the index of the back element may not be the the last element in the index table.

One way to resolve this is use priority queue instead of vector, this container will always give the biggest element, so index of last element should be popped after we swap while the constant complexity still holds. The idea is the same.

```
unordered_map<int,priority_queue<int>> m_index;
vector<int> nums;
RandomizedCollection() {
}
bool insert(int val) {
nums.push_back(val);
m_index[val].push(nums.size()-1);
return m_index[val].size()==1;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
if(m_index[val].empty())
return 0;
int index=m_index[val].top();
if(index==nums.size()-1){
nums.pop_back();
m_index[val].pop();
}
else{
nums[index]=nums.back();
m_index[nums.back()].push(index);
m_index[nums.back()].pop();
m_index[val].pop();
nums.pop_back();
}
return 1;
}
/** Get a random element from the collection. */
int getRandom() {
if(nums.empty())
return -1;
return nums[rand()%nums.size()];
}
```