Random Pick Index

lc 398

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

水塘抽样 http://blog.csdn.net/my_jobs/article/details/48372399

算法：

在取第i个数据的时候，我们生成一个0到i的随机数p，如果等于0（概率是1/i），保留第n个数。否则，继续保留前面的数。直到数据流结束，返回此数

ran.nextInt(n) will return an Integer in [0, n

public class Solution {
    int[] nums;
    Random ran;
    public Solution(int[] nums) {
        this.nums = nums;
        this.ran = new Random();
    }

    /*
For the nth target, ++count is n. Then the probability that rnd.nextInt(++count)==0 is 1/n. Thus, the probability that return nth target is 1/n.
For (n-1)th target, the probability of returning it is (n-1)/n * 1/(n-1)= 1/n.
*/


    public int pick(int target) {
        int count = 0; //to record how many targets in the array
        int result = -1;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != target) continue;
            if(ran.nextInt(++count) == 0 ){
                result = i;
            } 
        }
        return result;
    }
}