视频网站如何优化,nike官方网站定制,网站建设的策划书,比较好的友链平台提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣380. O(1) 时间插入、删除和获取随机元素二、力扣710. 黑名单中的随机数 前言 常数时间删除-查找数组中的任意元素#xff0c;且随机访问概率一致 如果… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣380. O(1) 时间插入、删除和获取随机元素二、力扣710. 黑名单中的随机数 前言 常数时间删除-查找数组中的任意元素且随机访问概率一致 如果想「等概率」且「在 O(1) 的时间」取出元素一定要满足底层用数组实现且数组必须是紧凑的。 这样我们就可以直接生成随机数作为索引从数组中取出该随机索引对应的元素作为随机元素。 但如果用数组存储元素的话插入删除的时间复杂度怎么可能是 O(1) 呢 可以做到对数组尾部进行插入和删除操作不会涉及数据搬移时间复杂度是 O(1)。 所以如果我们想在 O(1) 的时间删除数组中的某一个元素 val可以先把这个元素交换到数组的尾部然后再 pop 掉。 交换两个元素必须通过索引进行交换对吧那么我们需要一个哈希表 valToIndex 来记录每个元素值对应的索引。
一、力扣380. O(1) 时间插入、删除和获取随机元素
class RandomizedSet {private ListInteger nums;private MapInteger, 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;MapInteger,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();*/
