力扣labuladong——一刷day28

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

文章目录 前言一、力扣380. O(1) 时间插入、删除和获取随机元素二、力扣710. 黑名单中的随机数

---

前言

---

常数时间删除-查找数组中的任意元素，且随机访问概率一致 如果想「等概率」且「在 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(); */