这是六则或许对你有些许帮助的信息:

1、阿秀在工作之余开发了一个编程资源网站，目前已经收集了很多不错的学习资源和黑科技（附带下载地址），如你有意欢迎体验以及推荐自己认为不错的资源，众人拾柴火焰高，我为人人，人人为我🔥！

2、👉23年5月份我从字节跳动离职跳槽到某外企期间，为方便自己找工作，增加上岸几率，我自己从0开发了一个互联网中大厂面试真题解析网站，包括两个前端和一个后端。能够定向查看某些公司的某些岗位面试真题，比如我想查一下行业为互联网，公司为字节跳动，考察岗位为后端，考察时间为最近一年之类的面试题有哪些？

网站地址：InterviewGuide大厂面试真题解析网站。点此可以查看该网站的视频介绍：B站视频讲解 如果可以的话求个B站三连，感谢！

3、😊 分享一个学弟发给我的20T网盘资源合集，点此白嫖，主要是各类高清影视、电视剧、音乐、副业、纪录片、英语四六级考试、考研考公等资源。

4、😍免费分享阿秀个人学习计算机以来收集到的免费学习资源，点此白嫖；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏

5、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

6、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行不如一群人报团取暖，圈子里沉淀了很多过去21/22/23届学长学姐的经验和总结，好好跟着走下去的，最后基本都可以拿到不错的offer！此外，每周都会进行精华总结和分享！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载 。

380. 常数时间插入、删除和获取随机元素

力扣原题链接（点我直达） (opens new window)

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

1. insert(val)：当元素 val 不存在时，向集合中插入该项。
2. remove(val)：元素 val 存在时，从集合中移除该项。
3. getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

第一版，好差的一个数字...

执行用时 :284 ms, 在所有 cpp 提交中击败了5.15%的用户

内存消耗 :121.7 MB, 在所有 cpp 提交中击败了5.07%的用户

class RandomizedSet {
public:
	/** Initialize your data structure here. */
	RandomizedSet() {

	}

	/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
	bool insert(int val) {
		if (result.find(val) == result.end())
		{
			result.insert({ val,val });
			return true;
		}
		else
			return false;

	}

	/** Removes a value from the set. Returns true if the set contained the specified element. */
	bool remove(int val) {

		if (result.erase(val) == 1) return true;
		else
			return false;

	}

	/** Get a random element from the set. */
	int getRandom() {

		vector<int> temp;
		temp.reserve(result.size());
		for (auto beg = result.begin(); beg != result.end(); ++beg) {
			temp.push_back(beg->second);
		}

		int index = rand()%temp.size();

		return temp[index];
	}

private:
	unordered_map<int, int> result;
};

第二版，别人的做法，很有效

执行用时 :52 ms, 在所有 cpp 提交中击败了99.49%的用户

内存消耗 :22 MB, 在所有 cpp 提交中击败了78.34%的用户

首先，要在O(1)时间内的插入删除，肯定要利用哈希表的。但是问题在于随机返回一个元素，一开始还想着直接随机一个dict.size()范围内的数，然后让一个指向dict头部的迭代器与之相加-----------仔细一想，无序容器的迭代器不支持随机访问。。。但要随机返回某个元素，肯定要用到支持随机访问得迭代器啊！

而显然，支持随机访问的迭代器必须是管理连续内存的容器，常见的有--vector 、deque、C-stying arrary

所以目前需要(1)散列表(2)支持随机访问的迭代器，所以解法是，两者都用。 这里，用vector存储每一个插入的元素，散列表dict存储插入元素的下标。这样问题的关键就不是插入了，而是删除---怎样做到O(1)时间从vector容器内删除元素呢?显然，要从vector容器内删除元素，只能从其尾部删除。所以方法是:先交换vector队尾元素和待删除元素的值(因为dict中存储了下标，所以可以直接得到待删除元素的下标)，然后把队尾元素删除，并更新原队尾元素的下标即可，其他位置的元素下标并没有变化。

class RandomizedSet {
public:
	/** Initialize your data structure here. */
	RandomizedSet() {

	}

	/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
 bool insert(int val) {
        if(dict.count(val) > 0)
            return false;
        Numbers.push_back(val);
        dict[val] = Numbers.size()-1; 
        return true;
    }

	/** Removes a value from the set. Returns true if the set contained the specified element. */
	 bool remove(int val) {
        if(dict.count(val) == 0)
            return false;
        dict[Numbers.back()] = dict[val];               //更新原队尾元素的下标
        swap(Numbers.back(),Numbers[dict[val]]);        //交换原队尾元素和待删除元素
        Numbers.pop_back();                            //删除原队尾元素
        dict.erase(val);                               //删除指定元素的下标
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        int pos = Numbers.empty() ? 0 :rand() % Numbers.size();
        return Numbers[pos];
    }
private:
	unordered_map<int, int> dict;
    vector<int> Numbers
};

第三版，自己又复现一遍

执行用时 :68 ms, 在所有 cpp 提交中击败了84.10%的用户

内存消耗 :22.3 MB, 在所有 cpp 提交中击败了33.18%的用户

class RandomizedSet {
public:
	/** Initialize your data structure here. */
	RandomizedSet() {}

	/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
	bool insert(int val) {
		if (dict.find(val) == dict.end())//不在数组中
		{
			dict[val] = result.size();
			result.push_back(val);
			return true;
		}
		return false;

	}

	/** Removes a value from the set. Returns true if the set contained the specified element. */
	bool remove(int val) {

		if (dict.find(val) != dict.end()) {//在内存中		
			dict[result.back()] = dict[val];
			swap(result.back(),result[dict[val]]);
			dict.erase(val);
			result.pop_back();
			return true;
		}
			return false;


	}

	/** Get a random element from the set. */
	int getRandom() {

		int index = result.empty() ? 0 : rand() % result.size();
		return result[index];
	}

private:
	unordered_map<int, int> dict;
	vector<int> result;
};