LeetCode 380：插入删除GetRandom O（1）

Question

我遇到了这个leetcode问题Insert Delete GetRandom，在该问题中，它要求实现一种数据结构以在平均O（1）时间内支持Insert，Delete和getRandom，并将其解决为使用map和vector的情况。我的解决方案通过了除最后一个测试用例之外的所有测试用例，但我不知道为什么？最后一个测试用例确实非常大，无法调试。

我稍微修改了代码，然后通过了，但是仍然不知道为什么上一个未通过。

不可接受的解决方案：

class RandomizedSet {
map<int, int> mp;
vector<int> 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();
 */

解决方案：问题在于删除功能，当我通过以下代码更改删除功能时，它通过了。

    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。

两个版本的remove函数都可以处理极端情况-当地图中仅剩一个元素并且我们要删除它时。

LeetCode 380

Answer 1

这是因为当删除的元素是最后一个元素时，行为不确定。

例如，说操作是

insert(1) // v = [1], mp = [1->0]
insert(2) // v = [1,2], mp = [1->0, 2->1]
remove(2):

int idx = mp[val]; // val = 2, idx = 1
mp.erase(val); // mp = [1->0]
swap(v[idx], v[v.size()-1]); // idx = v.size()-1 = 1, so this does nothing.
v.pop_back(); // v = [1]
if(mp.size()!=0) mp[v[idx]] = idx; // mp[v[1]] = 1. 
// But v[1] is undefined after pop_back(), since v's size is 1 at this point.

我猜测它不会清除v [1]访问的内存位置，因此v [1]仍指向2，最终将2放回mp。