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

2023-12-25 06:07:50

哈希表 + 变长数组

  • 思路:
    • 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();
 */

文章来源:https://blog.csdn.net/N_BenBird/article/details/135176995
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。