这些问题的一个技巧点在于，如何结合哈希表和数组，使得数组的删除操作时间复杂度也变成 O(1)？下面来一道道看。
代码如下：
class RandomizedSet {
List list=new ArrayList<>();
Map map= new HashMap<>();
Random random= new Random();
public RandomizedSet() {
}
public boolean insert(int val) {
if (map.containsKey(val)){
return false;
}
list.add(val);
map.put(val,list.size()-1);
return true;
}
public boolean remove(int val) {
if (!map.containsKey(val)){
return false;
}
Integer index = map.get(val);
Integer last = list.get(list.size() - 1);
list.set(index,last);
list.remove(list.size()-1);
map.put(last,index);
map.remove(val);
return true;
}
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}
2避开黑名单的随机数
给你输入一个正整数 N，代表左闭右开区间 [0,N)，再给你输入一个数组 blacklist，其中包含一些「黑名单数字」，且 blacklist 中的数字都是区间 [0,N) 中的数字。
pick 函数会被多次调用，每次调用都要在区间 [0,N) 中「等概率随机」返回一个「不在 blacklist 中」的整数。
这应该不难理解吧，比如给你输入 N = 5, blacklist = [1,3]，那么多次调用 pick 函数，会等概率随机返回 0, 2, 4 中的某一个数字。
而且题目要求，在 pick 函数中应该尽可能少调用随机数生成函数 rand()。
这句话什么意思呢，比如说我们可能想出如下拍脑袋的解法：
int pick() {
int res = rand() % N;
while (res exists in blacklist) {
// 重新随机一个结果
res = rand() % N;
}
return res;
}
这个函数会多次调用 rand() 函数，执行效率竟然和随机数相关，不是一个漂亮的解法。
聪明的解法类似上一道题，我们可以将区间 [0,N) 看做一个数组，然后将 blacklist 中的元素移到数组的最末尾，同时用一个哈希表进行映射：
根据这个思路，我们可以写出第一版代码（还存在几处错误）：
class Solution {
public:
int sz;
unordered_map mapping;
Solution(int N, vector& blacklist) {
// 最终数组中的元素个数
sz = N - blacklist.size();
// 最后一个元素的索引
int last = N - 1;
// 将黑名单中的索引换到最后去
for (int b : blacklist) {
mapping[b] = last;
last--;
}
}
};
如上图，相当于把黑名单中的数字都交换到了区间 [sz, N) 中，同时把 [0, sz) 中的黑名单数字映射到了正常数字。
根据这个逻辑，我们可以写出 pick 函数：
int pick() {
// 随机选取一个索引
int index = rand() % sz;
// 这个索引命中了黑名单，
// 需要被映射到其他位置
if (mapping.count(index)) {
return mapping[index];
}
// 若没命中黑名单，则直接返回
return index;
}
这个 pick 函数已经没有问题了，但是构造函数还有两个问题。
第一个问题，如下这段代码：
int last = N - 1;
// 将黑名单中的索引换到最后去
for (int b : blacklist) {
mapping[b] = last;
last--;
}
我们将黑名单中的 b 映射到 last，但是我们能确定 last 不在 blacklist 中吗？
比如下图这种情况，我们的预期应该是 1 映射到 3，但是错误地映射到 4：
在对 mapping[b] 赋值时，要保证 last 一定不在 blacklist 中，可以如下操作：
// 构造函数 Solution(int N, vector& blacklist) { sz = N - blacklist.size(); // 先将所有黑名单数字加入 map for (int b : blacklist) { // 这里赋值多少都可以 // 目的仅仅是把键存进哈希表 // 方便快速判断数字是否在黑名单内 mapping[b] = 666; } int last = N - 1; for (int b : blacklist) { // 跳过所有黑名单中的数字 while (mapping.count(last)) { last--; } // 将黑名单中的索引映射到合法数字 mapping[b] = last; last--; } }
第二个问题，如果 blacklist 中的黑名单数字本身就存在区间 [sz, N) 中，那么就没必要在 mapping 中建立映射，比如这种情况：
我们根本不用管 4，只希望把 1 映射到 3，但是按照 blacklist 的顺序，会把 4 映射到 3，显然是错误的。
我们可以稍微修改一下，写出正确的解法代码：java版本
class Solution {
int sz;
Map map=new HashMap<>();
Random r = new Random();
public Solution(int n, int[] blacklist) {
sz=n-blacklist.length;
for (int i : blacklist) {
map.put(i,666);
}
int last =blacklist.length-1;
for (int i : blacklist) {
if (i>=sz){
continue;
}
while (map.containsKey(last)){
last--;
}
map.put(i,last);
last--;
}
}
public int pick() {
// 随机选取一个索引
int i = r.nextInt(sz);
return map.getOrDefault(i,i);
}
}
