importjava.util.Random;publicclassRandomizedSet {// Key : number// Value : corresponding index in arraylistMap<Integer,Integer> map;List<Integer> list;Random rd; /** Initialize your data structure here. */publicRandomizedSet() { map =newHashMap<Integer,Integer>(); list =newArrayList<Integer>(); rd =newRandom(); } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */publicbooleaninsert(int val) {// Set already has given valueif(map.containsKey(val)) returnfalse;map.put(val,list.size());list.add(val);returntrue; } /** Removes a value from the set. Returns true if the set contained the specified element. */publicbooleanremove(int val) {if(!map.containsKey(val)) returnfalse;int indexA =map.get(val);if(indexA !=list.size() -1) swap(list, map, indexA,list.size() -1);map.remove(list.get(list.size() -1));list.remove(list.size() -1);returntrue; } /** Get a random element from the set. */publicintgetRandom() {returnlist.get(rd.nextInt(list.size())); }// a : list index of element a// b : list index of element bprivatevoidswap(List<Integer> list,Map<Integer,Integer> map,int a,int b){int valA =list.get(a);int valB =list.get(b);int indexA =map.get(valA);int indexB =map.get(valB);list.set(a, valB);list.set(b, valA);map.put(valA, indexB);map.put(valB, indexA); }}
HashMap 的 value 只存一个 index 就不够用了,得存一个 Set<>,记录相同元素所有的 index,反正 add / remove 的平均复杂度都是 O(1)。
importjava.util.*;publicclassRandomizedCollection {Map<Integer,Set<Integer>> map;List<Integer> list;Random rand; /** Initialize your data structure here. */publicRandomizedCollection() { map =newHashMap<>(); list =newArrayList<>(); rand =newRandom(); } /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */publicbooleaninsert(int val) {boolean flag =false;if(!map.containsKey(val)){ flag =true;map.put(val,newHashSet<Integer>()); }list.add(val);map.get(val).add(list.size() -1);return flag; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */publicbooleanremove(int val) {boolean flag =false;if(map.containsKey(val) &&map.get(val).size() >0){ flag =true;int indexA =map.get(val).iterator().next();int indexB =list.size() -1;swap(map, list, indexA, indexB);map.get(val).remove(list.size() -1);list.remove(list.size() -1); }return flag; } /** Get a random element from the collection. */publicintgetRandom() {returnlist.get(rand.nextInt(list.size())); }// Swap elements at list index "a" and "b" in arraylist, and hashmapprivatevoidswap(Map<Integer,Set<Integer>> map,List<Integer> list,int indexA,int indexB){// O(1)int valA =list.get(indexA);int valB =list.get(indexB);// O(1) average map.get(valA).remove(indexA);map.get(valB).remove(indexB);// O(1) averagemap.get(valA).add(indexB);map.get(valB).add(indexA);// O(1)list.set(indexA, valB);list.set(indexB, valA); }}
问题二:运气不好,或者 blacklist 非常大的话,我们可能要调用多次 getRandom,而这个 API 可能是非常贵的。
因此另一个思考角度是,从 white list 出发。
对于【0,10】,blacklist = 【1,2,3,7,8】来讲,white list = 【0,4,5,6,9,10】.因此假设我们有足够内存去维护 whitelist,我们可以直接生成并返回一个 white list 中的元素,这样可以保证一次 getRandom() 操作保证得到想要的元素。
假如 white list 内存放不下呢?
方法照旧。每次我们生成一个 white list 的合理 index 之后,我们要找的就是 “第 index + 1 个不在 blacklist 中的数”。这个可以通过扫 blacklist 实现,O(1) 的内存开销。
相当于实现了一个 index -> whitelist[index] 的 mapping,可以保证一次 getRandom() 就可以得到有效元素。
i 从 0 到 n 循环,如果大于 blacklist 最后一个数,或者小于 blacklist 当前数,都 count --;
否则 blackPtr ++ ;
每次循环的时候,count 扣完了,当前 i 就是目标元素。
staticRandom rand =newRandom();publicstaticintgetRandom(int n,List<Integer> blackList){int totalNum = n +1;int whiteListSize = totalNum -blackList.size();int index =rand.nextInt(whiteListSize);int count = index +1;int blackPtr =0;for(int i =0; i <= n; i++){if(i >blackList.get(blackList.size() -1) || i <blackList.get(blackPtr)){ count --; } else { blackPtr ++; }if(count ==0) return i; }return-1; }publicstaticvoidmain(String[] args){List<Integer> blackList =newArrayList<Integer>();blackList.add(1);blackList.add(2);blackList.add(3);blackList.add(7);blackList.add(8);blackList.add(13);blackList.add(19);blackList.add(20);for(int i =0; i <50; i++){System.out.print(" , "+getRandom(20, blackList)); } }
importjava.util.*;publicclassSolution {ListNode head;ListNode rst;int count;Random rand; /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */publicSolution(ListNode head) {this.head= head; rand =newRandom(); } /** Returns a random node's value. */publicintgetRandom() {ListNode cur =head.next; rst = head; count =2;while(cur !=null){int num =rand.nextInt(count++);if(num ==0) rst = cur; cur =cur.next; }returnrst.val; }}
其原理非常类似于一群人在一个黑箱子里抽彩票,for 循环中的每次迭代相当于一个人,每次抽样范围 index = 箱子中剩下的所有彩票,其数量依次递减。到最后每个人虽然抽奖时箱子里彩票总数不同,但是获奖概率却是均等的。
importjava.util.*;publicclassSolution {int[] original;Random rand;publicSolution(int[] nums) { original = nums; rand =newRandom(); } /** Resets the array to its original configuration and return it. */publicint[] reset() {return original; } /** Returns a random shuffling of the array. */publicint[] shuffle() {int[] rst =Arrays.copyOf(original,original.length);for(int i =0; i <rst.length; i++){int index =rand.nextInt(rst.length- i) + i;int temp = rst[i]; rst[i] = rst[index]; rst[index] = temp; }return rst; }}