leetcode第710题黑名单中的随机数

基本思想:

将黑名单中的字符放在map里面,进行底层映射的调整,只要不是那个黑名单中的值就可以了

class Solution {
//总是感觉自己多少有点笨啊
    int sz;
    HashMap map;
    Random random;
    public Solution(int n, int[] blacklist) {
        sz = n - blacklist.length;
        map = new HashMap();
        random = new Random();
        for(int b : blacklist){
            map.put(b,666);
        }
        int last = n - 1;
        for(int b : blacklist){
            if(b >= sz){
                continue;
            }
            //对map中的数字进行正确的映射
            while(map.containsKey(last)){
                last--;
            }
            map.put(b,last);
            last--;
        }
    }
    
    public int pick() {
        int index = random.nextInt(100) % sz;

        //如果命中黑名单,就映射到其他的位置
        if(map.containsKey(index)){
            return map.get(index);
        }
        //如果没有命中,直接进行返回
        return index;
    }
}