Simple Java Reservoir Sampling Solution


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

  • 0
    M

    A lil confused. Why do you check for rand.nextInt(count++)==0 ?
    I see you generate a random number between 0 and count(exclusive) but why check that?
    rand.nextInt(1) <-- 0
    rand.nextInt(2) <-- random num between 0 and 1
    rand.nextInt(3) <-- random num between 0 and 2
    rand.nextInt(4) <-- random num between 0 and 3


  • 0
    C

    @modqhx To make sure probability is 1/n
    Think of that: if there is only one digit, the only random number has to be 0.
    How about two, three, four? in order to make sure we have equal probability, 0 is one good and valid indicator the rest number has same probability as first matches number.
    Be aware that, random number has nothing to do with the number in the array. We just use that random number to know whether current number has same probablity ..


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.