力扣解题思路：蓄水池抽样

给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据。

这个场景强调了3件事：
1.数据流长度N很大且不可知，所以不能一次性存入内存。
2.时间复杂度为O(N)。
3.随机选取m个数，每个数被选中的概率为m/N。

第1点限制了不能直接取N内的m个随机数，然后按索引取出数据。第2点限制了不能先遍历一遍，然后分块存储数据，再随机选取。第3点是数据选取绝对随机的保证。

算法思路大致如下：

1.如果接收的数据量小于m，则依次放入蓄水池。
2.当接收到第i个数据时，i >= m，在[0, i]范围内取以随机数d，若d的落在[0, m-1]范围内，则用接收到的第i个数据替换蓄水池中的第d个数据。
3.重复步骤2。

当处理完所有的数据时，蓄水池中的每个数据都是以m/N的概率获得的。
接下来看代码：

int[] reservoir = new int[m];
//init
for (int i = 0; i < reservoir.length; i++){
 reservoir[i] = dataStream[i];
}
for (int i = m; i < dataStream.length; i++){
 // 随机获得一个[0, i]内的随机整数
 int d = rand.nextInt(i + 1);
 // 如果随机整数落在[0, m-1]范围内，则替换蓄水池中的元素
 if (d < m){
     reservoir[d] = dataStream[i];
 }
}

还有文章中提到的分布式蓄水池抽样，可以看一下~：

思路：

大多是人的解法就是遍历一遍所有数据，然后生成随机数得到该节点：

class Solution {
    int max = 0;
    private ListNode root = null;
    public Solution(ListNode head) {
        root = head;
        while (head != null){
            max++;
            head = head.next;
        }
    }
    public int getRandom() {
        int i = (int) (Math.random() * max) + 1;
        int val = 0;
        ListNode node = root;
        for (int j = 0; j < i; j++) {
            val = node.val;
            node = node.next;
        }
        return val;
    }
}

实际上题目想说的就是，只遍历一遍得出结果，这就必须用到蓄水池抽样了：

class Solution {
    private ListNode head;
    public Solution(ListNode head) {
       this.head = head;
    }
    public int getRandom() {
        int res = head.val;
        ListNode no = head.next;
        int i = 2;//蓄水池大小为1
        Random random = new Random();
        while(no!=null){
            if(random.nextInt(i) == 0){//替换蓄水池中元素
                res = no.val;
                //return res;
            }
            i++;
            no = no.next;
        }
        return res;

    }
}

思路：
首先暴力法：

class Solution {
    private HashMap<Integer,ArrayList<Integer>> pos;
    Random rand;
    public Solution(int[] nums) {
        pos = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(!pos.containsKey(nums[i])){
                pos.put(nums[i],new ArrayList<Integer>());
            }
            pos.get(nums[i]).add(i);
        }    
        rand = new Random();
    }
    public int pick(int target) {
        ArrayList<Integer> arr = pos.get(target);
        if(arr==null) return -1;
        return arr.get(rand.nextInt(arr.size()));
    }
}

蓄水池抽样：

class Solution {
    int[] nums;
    public Solution(int[] nums) {
        this.nums = nums;
    }
    public int pick(int target) {
        Random rand = new Random();
        int c = 0;
        int index = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i] == target){
                c++;
                if(rand.nextInt(c) == 0) index = i;
            }
        }
        return index;
    }
}

今天上午脑子抽了把this.nums = nums;写成了nums = this.nums;然后pick方法一直报空指针异常我寻思我没写错啊咋就报错了。。。?