Why not this straight forward solution?

  • 1

    I didn't see any performance difference with this solution https://discuss.leetcode.com/topic/58301/simple-reservoir-sampling-solution?page=1

    I think the question is not clear, it only requires "randomly output the index of a given target number", but not make it clear whether the probability should be 1/(number of target) or 1/(number of whole array numbers)

    class Solution {
        Random random;
        int[] origin;
        public Solution(int[] nums) {
            random = new Random();
            origin = nums;
        public int pick(int target) {
                int idx = random.nextInt(origin.length);
                if(origin[idx] == target){
                    return idx;

  • 0

    Hmm, O(1) extra space, expected O(n) time per pick... I wish I had thought of this :-)

    But how could the probability be 1/(number of whole array numbers)? As soon as the array has different values, that wouldn't add up to 1.

Log in to reply

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