Leetcode-710. 黑名单中的随机数

710. 黑名单中的随机数
给定一个包含 [0，n ) 中独特的整数的黑名单 B，写一个函数从 [ 0，n ) 中返回一个不在 B 中的随机整数。

对它进行优化使其尽量少调用系统方法 Math.random() 。

提示:

1 <= N <= 1000000000
0 <= B.length < min(100000, N)
[0, N) 不包含 N，详细参见 interval notation 。
示例 1:

输入:
["Solution","pick","pick","pick"]
[[1,[]],[],[],[]]
输出: [null,0,0,0]
示例 2:

输入:
["Solution","pick","pick","pick"]
[[2,[]],[],[],[]]
输出: [null,1,1,1]
示例 3:

输入:
["Solution","pick","pick","pick"]
[[3,[1]],[],[],[]]
Output: [null,0,0,2]
示例 4:

输入:
["Solution","pick","pick","pick"]
[[4,[2]],[],[],[]]
输出: [null,1,3,1]

解题思路
利用逻辑上的紧凑数组实现
N个数中，加入有m个黑名单。则将非黑名单的数字逻辑上存放在前N-m中。这样可以通过随机索引保证随机
如果黑名单在前半部分，则与后半部分的值交换---此时用map存index到val的映射。其他正常的index=val。则不用再次存储
ps：代码看了好几遍没问题，但是运行不过
试运行结果正确，提交时又不通过。同样的用例。之后再看
java代码

class Solution {
    public static int sz;
    public static Map<Integer,Integer> map=new HashMap<>();

    public Solution(int N, int[] blacklist) {
        for(int b:blacklist){
            map.put(b,-1);
        }
        sz=N-blacklist.length;
        int last=N-1;
        for(int b:blacklist){
            if(b>=sz){
                continue;
            }
            //找到未在前方的最后一个正常数
            while(map.containsKey(last)){
                last--;
            }
            //交换
            map.put(b,last);
            //舍弃交换后的黑名单
            last--;
        }
    }

    public int pick() {
        int index=(int)(Math.random()*sz);
        //交换过的数在map中，其他的就等于index
        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();
 */