题目描述

实现RandomizedSet 类:

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

链接:https://leetcode-cn.com/problems/insert-delete-getrandom-o1

思路

  1. 要求常数时间内完成插入删除操作显然可以使用 map.
  2. 如果要求在O(1)内完成数据的随机访问,得用vector这类容器.

如果使用vector存储数据的话,显然可以完成常数时间内插入和随机访问的任务,但是删除指定元素呢?

对于顺序表而言,删除数据后会花费大量时间在整理空间上面,如果要删除的每个元素都在末尾那么就可以避免这个问题了.

由此可以得出,可以尝试用map存储val与index的对应关系,当需要删除元素的时候,先将元素与末尾元素进行位置调整,再进行删除.

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
class RandomizedSet {
public:
unordered_map<int,int> hash;
vector<int>nums;

RandomizedSet() {

}

bool insert(int val) {
if(hash.count(x)==0){
nums.push_back(x);
hash[x]=nums.size()-1;
return true;
}
}

bool remove(int val) {
if(hash.count(x)){
int y = nums.back();
int px = hash[x],py=hash[y];
swap(nums[px],nums[py]);
swap(hash[x],hash[y]);//交换vector值之后千万不要忘记交换hash值
nums.pop_back();
hash.erase(x);
return true;
}
}

int getRandom() {
return nums[rand()% nums.size()]//直接使用rand()(伪随机)
}
};

执行耗时 184ms,击败85.96% user
内存消耗 94.7MB,击败58.19%