LeetCode算法小抄--O(1)时间下删除-查找数组中任意元素

⚠申明： 未经许可，禁止以任何形式转载，若要引用，请标注链接地址。 全文共计3489字，阅读大概需要3分钟
🌈更多学习内容， 欢迎👏关注👀【文末】我的个人微信公众号：不懂开发的程序猿
个人网站：https://jerry-jy.co/

O(1)时间下删除-查找数组中任意元素

380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

• RandomizedSet() 初始化 RandomizedSet 对象
• bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
• bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
• int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

本题的难点在于两点：

1、插入，删除，获取随机元素这三个操作的时间复杂度必须都是 O(1)。

2、getRandom 方法返回的元素必须等概率返回随机元素，也就是说，如果集合里面有 n 个元素，每个元素被返回的概率必须是 1/n。

分析：

1、对于插入，删除，查找这几个操作，哪种数据结构的时间复杂度是 O(1)？

HashSet 算一个，哈希集合的底层原理就是一个大数组，我们把元素通过哈希函数映射到一个索引上；如果用拉链法解决哈希冲突，那么这个索引可能连着一个链表或者红黑树。HashSet做不到 O(1) 时间「等概率」随机获取元素。LinkedHashSet也不能满足要求

2、对于 getRandom 方法，如果想「等概率」且「在 O(1) 的时间」取出元素，一定要满足：底层用数组实现，且数组必须是紧凑的。可以直接生成随机数作为索引，从数组中取出该随机索引对应的元素，作为随机元素

3、但如果用数组存储元素的话，插入，删除的时间复杂度怎么可能是 O(1) 呢？

可以做到！对数组尾部进行插入和删除操作不会涉及数据搬移，时间复杂度是 O(1)。

所以，如果我们想在 O(1) 的时间删除数组中的某一个元素 val，可以先把这个元素交换到数组的尾部，然后再 pop 掉。交换两个元素必须通过索引进行交换对吧，那么我们需要一个哈希表 valToIndex 来记录每个元素值对应的索引。

class RandomizedSet {// 存储元素的值List<Integer> nums;// 记录每个元素对应在 nums 中的索引Map<Integer, Integer> valToIndex;public RandomizedSet() {nums = new ArrayList<>();valToIndex = new HashMap<>();}public boolean insert(int val) {// 若 val 已存在，不用再插入if (valToIndex.containsKey(val)) {return false;}// 若 val 不存在，插入到 nums 尾部，// 并记录 val 对应的索引值valToIndex.put(val, nums.size());nums.add(val);return true;        }public boolean remove(int val) {// 若 val 不存在，不用再删除if (!valToIndex.containsKey(val)) {return false;}// 先拿到 val 的索引int index = valToIndex.get(val);// 将最后一个元素对应的索引修改为 indexvalToIndex.put(nums.get(nums.size() - 1), index);// 交换 val 和最后一个元素Collections.swap(nums, index, nums.size() - 1);// 在数组中删除元素 valnums.remove(nums.size() - 1);// 删除元素 val 对应的索引valToIndex.remove(val);return true;}public int getRandom() {// 随机获取 nums 中的一个元素return nums.get((int) (Math.random() * nums.size()));        }
}

注意 remove(val) 函数，对 nums 进行插入、删除、交换时，都要记得修改哈希表 valToIndex，否则会出现错误。

每个操作的复杂度都是 O(1)，且随机抽取的元素概率是相等的。

710. 黑名单中的随机数[hard]

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法，使它最小化调用语言 内置 随机函数的次数。

实现 Solution 类:

• Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
• int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数

翻译：pick 函数会被多次调用，每次调用都要在区间 [0,N) 中「等概率随机」返回一个「不在 blacklist 中」的整数。要求，在 pick 函数中应该尽可能少调用随机数生成函数 rand()。

思路：可以将区间 [0,N) 看做一个数组，然后将 blacklist 中的元素移到数组的最末尾，同时用一个哈希表进行映射：

/* 根据黑名单生成的随机数*/
class Solution {// 最终紧凑数组中的元素个数int sz;// mapping 用于记录哪些黑名单索引需要被替换成白名单索引Map<Integer, Integer> mapping;/* 构造函数，时间复杂度 O(n)* * @param N         数组中的元素个数* @param blacklist 黑名单中的元素索引集合*/public Solution(int N, int[] blacklist) {sz = N - blacklist.length;mapping = new HashMap<>();// 先将所有黑名单数字加入 mapfor (int b : blacklist) {// 这里value赋值多少都可以// 目的仅仅是把键存进哈希表// 方便快速判断数字是否在黑名单内            mapping.put(b, 666);}int last = N - 1;for (int b : blacklist) {// 如果 b 已经在区间 [sz, N)// 可以直接忽略if (b >= sz) {continue;}while (mapping.containsKey(last)) {last--;}// 将黑名单中的索引映射到合法数字mapping.put(b, last);last--;}}/* 获取随机数，时间复杂度 O(logn)* * @return 随机数*/public int pick() {// 随机选取一个索引int index = (int)(Math.random() * sz);// 这个索引命中了黑名单，// 需要被映射到其他位置if (mapping.containsKey(index)) {return mapping.get(index);}// 若没命中黑名单，则直接返回return index;}
}/* Your Solution object will be instantiated and called as such:* Solution obj = new Solution(n, blacklist);* int param_1 = obj.pick();*/

总结：

1、如果想高效地，等概率地随机获取元素，就要使用数组作为底层容器。

2、如果要保持数组元素的紧凑性，可以把待删除元素换到最后，然后 pop 掉末尾的元素，这样时间复杂度就是 O(1) 了。当然，我们需要额外的哈希表记录值到索引的映射。

3、对于数组中含有「空洞」（黑名单数字），也可以利用哈希表巧妙处理映射关系，让数组在逻辑上是紧凑的，方便随机取元素。

–end–