LeetCode 380: Вставить Удалить GetRandom O (1) ⇐ C++

[Anonymous]

Я столкнулся с этой проблемой с лит-кодом Insert Delete GetRandom, где меня попросили реализовать структуру данных для поддержки вставки, удаления и getRandom в среднем за время O (1), и решил ее, используя карту и вектор.
Мое решение проходит все тестовые случаи, кроме последнего, и я не могу понять, почему? Последний тестовый пример действительно очень большой для отладки.

Я немного изменил свой код, и затем он прошел, но до сих пор не понял, почему предыдущий не прошел. пройти.

Непринятое решение:

Код: Выделить всё

class RandomizedSet {
map mp;
vector v;

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(mp.find(val) == mp.end()){

v.push_back(val);
mp[val] = v.size()-1;
return true;
}
else return false;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
if(mp.find(val) == mp.end()){
return false;
}
else{
int idx = mp[val];
mp.erase(val);
swap(v[idx], v[v.size()-1]);
v.pop_back();
if(mp.size()!=0) mp[v[idx]] = idx;

return true;
}
}

/** Get a random element from the set. */
int getRandom() {
if(v.size() == 0) return 0;
int rndm = rand()%v.size();
return v[rndm];
}
};

/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/

Принятое решение:
Проблема заключается в функции удаления: когда я изменяю функцию удаления с помощью приведенного ниже кода, она проходит.< /p>

Код: Выделить всё

    if(mp.find(val) == mp.end()){
return false;
}
else{
int idx = mp[val];

swap(v[idx], v[v.size()-1]);
v.pop_back();
mp[v[idx]] = idx;
mp.erase(val);
return true;
}

Я не понимаю, почему это происходит. Я поместил mp.erase(val) в последнее место и заменил if(mp.size()!=0) mp[v[idx]] = idx на mp[v[idx] ] = только idx.

Обе версии функции удаления могут обрабатывать угловой случай — когда на карте остался только один элемент, и мы хотим удалите его.

LeetCode 380

Подробнее здесь: https://stackoverflow.com/questions/623 ... trandom-o1