LC380-O(1) 时间插入、删除和获取随机元素

380. O(1) 时间插入、删除和获取随机元素

class RandomizedSet {
public:
    unordered_maphash;
    vectornums;

    // 使用哈希表支持O(1)插入删除
    // 使用数组配合支持随机索引
    RandomizedSet() {

    }
    
    bool insert(int val) {
        if(hash.count(val)) return false;

        nums.push_back(val);
        hash[val] = nums.size() - 1;

        return true;
    }
    
    bool remove(int val) {
        if(!hash.count(val)) return false;

        int x = val, y = nums.back();
        int px = hash[x], py = hash[y];
        swap(nums[px], nums[py]);
        nums.pop_back();
        swap(hash[x], hash[y]);
        hash.erase(x); 

        return true;
    }
    
    int getRandom() {
        return nums[rand() % nums.size()];
    }
};