LeetCode 380 Insert Delete GetRandom O(1)

    
        标签：
        
            设计数据结构
        
            LeetCode
        
    发布于：2022-02-13 14:45:33
    编辑于：2022-02-13 15:06:16
    浏览量：1071

概述

https://leetcode.com/problems/insert-delete-getrandom-o1/

哈希表 + 数组

为了 O(1) 的访问一个随机元素，我们可以考虑使用数组。

又为了插入和删除也是 O(1)，考虑使用哈希表，值存其在数组中的索引即可。

插入的时候直接插入即可，删除的时候其与尾部元素交换位置，再删。

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

Links: leetcode-380-insert-delete-getrandom-o(1)