# 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();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 第一版,好差的一个数字...

执行用时 :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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# 第二版,别人的做法,很有效

执行用时 :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
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 第三版,自己又复现一遍

执行用时 :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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43