Concise Java solution using Reservoir Sampling beat 91%


  • 0
    A

    Scan the array and whenever find a target number, resample it with 1/count possibility.

    Can easily achieve by Java built in Random.nextInt(int n)

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

Log in to reply
 

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