Share my simple Java solution


  • 2

    If we have int[] nums = [1,2,3,1,1,1,1,1], using r.nextInt(n) will give us a random int between [0, n) (exclusive), so each number in nums has 1/n probability to be returned.

    Thus, numbers equal to target share the same probability.

    public class Solution {
        int[] nums;
        Random r;
        public Solution(int[] nums) {
            this.nums = nums;
            r = new Random();
        }
        
        public int pick(int target) {
            int size = nums.length;
            int i = r.nextInt(size);
            while (nums[i] != target) {
                i = r.nextInt(size);
            }
            
            return i;
        }
    }
    
    

  • 0
    B

    Correct me if I'm wrong.
    I think your code not reservoir sampling.
    It says "The array size can be very large", which means the input is a stream with infinite length. So you cannot assume length is known. The reservoir sampling algorithm does not require length of input. Pls check this wiki page: https://en.wikipedia.org/wiki/Reservoir_sampling


  • 0

    Hi @BBQ, Thanks for pointing out! I think you are right.


Log in to reply
 

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