Share my simple Java solution


  • 3

    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.


  • 0
    Z

    @BBQ I think you are right. BTW, do you have any idea about the time complexity of this algorithm?


Log in to reply
 

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