1时间插入、删除和获取随机元素
?
这些问题的一个技巧点在于，如何结合哈希表和数组，使得数组的删除操作时间复杂度也变成 O(1)？下面来一道道看。
代码如下：
class RandomizedSet {
List<Integer> list=new ArrayList<>();
Map<Integer,Integer> 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<int, int> mapping;
Solution(int N, vector<int>& 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<int>& 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<Integer,Integer> 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);
}
}
