Reservoir Sampling Solution


  • 0
    Y

    Reservoir sampling is usually used to randomly pick up k elements in an array S with very big size N or in a data stream S with the same probability. The idea of the algorithm is:

    (1) Get the first k elements from S and put them into an array result[]
    (2) for j >= k && j < N:
    generate a random number r [0, j]
    if r < k: result[r] = S[j]

    For this question, we can take k = 1, and we only care about the number whose value equals target. First, keep an array of size 1 (just a variable V works).Then assign the first index of the target to it. We can loop every element in input, and at the meantime, use a count to record how many target we've seen now (same role as j). Then generate a random number [0, count). If the number == 0, we can replace the V's value with the new index. After visiting every element in S, the V's value is what we want.

    You may wonder, why Reservoir Sampling can guarantee the equal possibility. Let's take a look at the original problem and solution. When we see element S[j], the possibility of choosing it into the reservoir is k/j, and the possibility of its being replaced by ONE elements(t, t > j) later is (k/t)/k = 1/t. Therefore, the probability of S[j] not being replaced by ANY OTHER elements later in S is:
    (1 - 1/(j + 1)) * (1 - 1/(j + 2)) * ......* (1 - 1/N) = j/N
    Therefore, the posibiility of S[j] is in the Reservoir is
    k/j * j/N = k/N

    The code for this specific problem is :

    public class Solution {
        int[] input;
        public Solution(int[] nums) {
            input = nums;
        }
    
        public int pick(int target) {
             int resevoir = -1;
             int cnt = 0;
             for(int i = 0; i < input.length; i++){
                 if(input[i] == target){
                     cnt++;
                     Random rand = new Random();
                     int random = rand.nextInt(cnt);
                     
                     if(random == 0){
                         resevoir = i;
                     }
                 }
             }
             
             return resevoir;
        }
    }
    
    

Log in to reply
 

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