程序分享--大厂常见算法/编程面试题：O(1) 时间插入、删除和获取随机元素

关注我，持续分享逻辑思维&管理思维&面试题； 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导；
有意找工作的同学，请参考博主的原创：《面试官心得--面试前应该如何准备》，《面试官心得--面试时如何进行自我介绍》， 《做好面试准备，迎接2024金三银四》。
或关注博主免费专栏【程序员宝典--常用代码分享】里面有大量面试涉及的算法或数据结构编程题。

-------------------------------------正文----------------------------------------

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

-------------------------------------答案----------------------------------------

class RandomizedSet {
private:
    unordered_map<int,int> hashmap;
    int nums[200010];
    int idx;
public:
    RandomizedSet() {
        srand((unsigned)time(NULL));
        idx = -1;
    }
    
    bool insert(int val) {
        if(hashmap.find(val) != hashmap.end()) {
            return false;
        }
        nums[++idx]  = val;
        hashmap[val] = idx;
        return true;
    }
    
    bool remove(int val) {
        if(hashmap.find(val) != hashmap.end()) {
            return false;
        }
        int tail = nums[idx];
        int rm_idx = hashmap[val];
        swap(nums[rm_idx],nums[idx]);

        hashmap.erase(val);
        if(val != tail) hashmap[tail] = rm_idx;
        idx--;
        return true;
    }
    
    int getRandom() {
        int random_i = rand() % (idx+1);
        return nums[random_i];
    }
};

感兴趣的同学辛苦 关注/点赞 ，持续分享逻辑、算法、管理、技术、人工智能相关的文章。

博主其它经典原创：《管理心得--如何高效进行跨部门合作》，《技术心得--如何成为优秀的架构师》、《管理心得--如何成为优秀的架构师》、《管理心理--程序员如何选择职业赛道》，及
《C#实例：SQL如何添加数据》，《C#实战分享--爬虫的基础原理及实现》欢迎大家阅读。