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

哈希表 + 变长数组

• 思路：
  • O(1) 插入、删除想到的是哈希表，但是不能 O(1) 获取随机元素；
  • 变长数组可以 O(1) 获取随机元素但是不能 O(1) 插入和删除；
  • 需要结合这两个数据结构，将数据存放在 vector 中，用哈希表来记录其索引；

class RandomizedSet {
public:
    RandomizedSet() {
        srand((unsigned)time(NULL));
    }
    
    bool insert(int val) {
        if (idx_.count(val)) {
            return false;
        }

        int index = data_.size();
        data_.emplace_back(val);
        idx_[val] = index;

        return true;
    }
    
    bool remove(int val) {
        if (idx_.count(val) == 0) {
            return false;
        }

        int index = idx_[val];
        int last_val = data_.back();
        data_[index] = last_val;
        idx_[last_val] = index;
        data_.pop_back();
        idx_.erase(val);

        return true;
    }
    
    int getRandom() {
        int rndIdx = rand() % data_.size();
        return data_[rndIdx];
    }

private:
    std::vector<int> data_;
    std::unordered_map<int, int> idx_;
};

/**
 * 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();
 */