LeetCode 380：插入删除GetRandom O(1)

Question

我遇到了这个 leetcode 问题 Insert Delete GetRandom，要求在平均 O(1) 时间内实现一个数据结构以支持插入、删除和 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。

LeetCode 380：插入删除GetRandom O(1)

LeetCode 380: Insert Delete GetRandom O(1)

c++

algorithm

data-structures

testcase