LeetCode 380. 常数时间插入、删除和获取随机元素（哈希+vector）

Michael阿明

发布于 2020-07-13 15:25:15

4550

发布于 2020-07-13 15:25:15

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 题目

设计一个支持在平均时间复杂度 O(1) 下，执行以下操作的数据结构。

insert(val)：当元素 val 不存在时，向集合中插入该项。 remove(val)：元素 val 存在时，从集合中移除该项。 getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

哈希表 key存储数据，value存储其在vector中的下标
删除时，先把vector尾部的数存到要删除的位置

class RandomizedSet {
    vector<int> v;
    unordered_map<int,int> m;
public:
    RandomizedSet() { }
    
    bool insert(int val) {
        if(m.find(val) == m.end())
        {
            m[val] = v.size();
            v.push_back(val);
            return true;
        }
        else
            return false;
    }
    
    bool remove(int val) {
        if(m.find(val) == m.end())
            return false;
        v[m[val]] = v.back();
        m[v.back()] = m[val];
        v.pop_back();
        m.erase(val);
        return true;
    }
    
    int getRandom() {
        if(v.size() == 0)
            return -1;
        return v[rand() % v.size()];
    }
};