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); // 将最后一个元素对应的索引修改为 index valToIndex.put(nums.get(nums.size() - 1), index); // 交换 val 和最后一个元素 Collections.swap(nums, index, nums.size() - 1); // 在数组中删除元素 val nums.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<>(); // 先将所有黑名单数字加入 map for (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–
