LeetCode 380 Insert Delete GetRandom O(1)

Tag: 设计数据结构 LeetCode Posted on 2022-02-13 14:45:33 Edited on 2022-02-13 15:06:16 Views: 147

概述

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()];
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/