思路:使用底层用数组实现的,插入时在尾部插入,删除时将待删除元素交换到数组的尾部,再pop
-
LeetCode380 O(1)时间插入、删除和获取随机元素
-
思路分析
- 本题难点有两点
- 插入、删除、随机获取元素这三个操作的时间复杂度都必须为O(1)
- getRandom方法必须等概率返回元素
- 解决策略
- 针对O(1):
- 底层用数组实现,且数组必须是紧凑的,这样用随机数生成索引,getRandom等概率返回元素
- 插入和删除:如何使用数组插入、删除时间复杂度为O(1),即将要删除的元素替换为数组最后一个元素,并将数组最后一个元素删除,因此需要一个HashMap记录索引
- 针对O(1):
- 本题难点有两点
-
代码实现
-
class RandomizedSet { private Listlist; private HashMap valToIndex; private Random random; public RandomizedSet() { list = new ArrayList<>(); valToIndex = new HashMap<>(); random = new Random(); } public boolean insert(int val) { if (valToIndex.containsKey(val)) { return false; } int index = list.size(); list.add(val); valToIndex.put(val, index); return true; } public boolean remove(int val) { if (!valToIndex.containsKey(val)) { return false; } //获取待删除元素的索引 int delIndex = valToIndex.get(val); //获取最后一个元素的值 int lastVal = list.get(list.size() - 1); //将待删除元素替换为最后一个元素 list.set(delIndex, lastVal); //在数组中删除最后一个元素 list.remove(list.size() - 1); //更新valToIndex中,注意是key是val,value是Index valToIndex.put(lastVal, delIndex); valToIndex.remove(val); return true; } public int getRandom() { return list.get((int)(random.nextInt(list.size()))); } }
-
-
LeetCode710 黑名单中的随机数
-
思路分析
-
题目分析
要求我们在[0, n-1]中排除掉黑名单数组后等概率返回剩余某一个数
例如:输入N = 5, blacklist = [1, 3],多次调用pick函数,会等概率随机返回0,2,4中的某一个数
且题目要求使用最少的random
-
解题思路
-
与上一题类似,我们可以将区间[0, N]看作一个数组,然后将blacklist中的元素移到数组中的最末尾last = N -1,同时用一个哈希表进行映射,相当于把黑名单中的数和size之后不是黑名单的数替换
细节
- 如果last在黑名单中,则直接跳过
- 如果b >= size, 即b在[size, N - 1]数组中,就没有必要建立映射
- 将黑名单中的索引映射到合法数字
-
排除黑名单数组后的数组个数size = N - blacklist.size(); 则黑名单中的数字都交换到了[sz, N - 1]区间,[0, sz - 1]中的黑名单数字映射到了正常数字
-
HashMap中的key是黑名单元素,value是正常元素索引,如图所示
-
关于pick函数,随机生成[0, size)之间的整数n,如果n是黑名单元素如1,则返回4;如n不是黑名单元素则返回n,例如0 和 2
-
-
-
代码实现
class Solution { private int size; private HashMapmap; public Solution(int n, int[] blacklist) { size = n - blacklist.length; map = new HashMap<>(); int last = n - 1; //将blacklist放入到map,以便查找 for(int b : blacklist) { map.put(b, -1); } for(int b : blacklist) { //b在[size, N - 1]数组中,没有必要建立映射 if (b >= size) { continue; } //last在黑名单中,直接跳过 while (map.containsKey(last)) { last--; } map.put(b, last); last--; } } public int pick() { int index = (int)(Math.random() * size); //若index在黑名单中,则返回map.get(index);否则返回index return map.getOrDefault(index, index); } }
-



