c++ - LeetCode 380:插入删除 GetRandom O(1)
问题描述
我遇到了这个 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
两个版本的删除函数都能够处理极端情况 - 当地图中只剩下一个元素并且我们想要删除它时。
解决方案
这是因为当移除的元素是最后一个元素时的未定义行为。
例如,假设操作是
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。
推荐阅读
- reactjs - 使用 Redux 和 React Hooks,Flatlist 不会重新渲染,也不会重新渲染其中的单个组件
- python - 在 Python 中创建静态类
- php - 使用插值变量注入 JSON 字符串不起作用
- java - RESTful 服务 URL 中的分号截断它后面的字符
- web-scraping - 如何知道哪个公司保护网站?
- vue.js - Vue.js:@input 用于不使用 v-for
- javascript - 如何在面试中回答“Javascript 中的原型继承与经典继承有何不同”?
- python - 基于每行类别的熊猫样本
- .htaccess - 如何使用 .htaccess 创建友好的 url
- xcode - UIActivityViewController 标识为我的 Mac Catalyst 应用程序的非公共 API