力扣labuladong——一刷day28

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

常数时间删除-查找数组中的任意元素，且随机访问概率一致
如果想「等概率」且「在 O(1) 的时间」取出元素，一定要满足：底层用数组实现，且数组必须是紧凑的。 这样我们就可以直接生成随机数作为索引，从数组中取出该随机索引对应的元素，作为随机元素。 但如果用数组存储元素的话，插入，删除的时间复杂度怎么可能是 O(1) 呢？ 可以做到！对数组尾部进行插入和删除操作不会涉及数据搬移，时间复杂度是 O(1)。 所以，如果我们想在 O(1) 的时间删除数组中的某一个元素 val，可以先把这个元素交换到数组的尾部，然后再 pop 掉。 交换两个元素必须通过索引进行交换对吧，那么我们需要一个哈希表 valToIndex 来记录每个元素值对应的索引。

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

class RandomizedSet {private List<Integer> nums;private Map<Integer, Integer> valToIndex;public RandomizedSet() {nums = new ArrayList<>();valToIndex = new HashMap<>();}public boolean insert(int val) {if(valToIndex.containsKey(val)){return false;}nums.add(val);valToIndex.put(val,nums.size()-1);return true;}public boolean remove(int val) {if(!valToIndex.containsKey(val)){return false;}int deleteIndex = valToIndex.get(val);int curIndex = nums.size()-1;Collections.swap(nums, deleteIndex, curIndex);valToIndex.put(nums.get(deleteIndex),deleteIndex);nums.remove(nums.size()-1);valToIndex.remove(val);return true;}public int getRandom() {return nums.get((int)(Math.random()*nums.size()));}
}/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet obj = new RandomizedSet();* boolean param_1 = obj.insert(val);* boolean param_2 = obj.remove(val);* int param_3 = obj.getRandom();*/

二、力扣710. 黑名单中的随机数

class Solution {int RZ;Map<Integer,Integer> map;public Solution(int n, int[] blacklist) {RZ = n - blacklist.length;map = new HashMap<>();for(int b : blacklist){map.put(b,666);}int last = n-1;for(int b : blacklist){if(b >= RZ){continue;}while(map.containsKey(last)){last --;}map.put(b,last);last --;}}public int pick() {int index = (int)(Math.random()*RZ);if(map.containsKey(index)){return map.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();*/