398. Random Pick Index[Sampling Algo]

Version #2 Reservoir Sampling
https://www.geeksforgeeks.org/reservoir-sampling/

26.07 %
class Solution {
    Random rd;
    int[] nums;
    public Solution(int[] nums) {
        this.rd = new Random();
        this.nums = nums;
    }
   
    public int pick(int target) {
        int count = 0;
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != target) continue;
            count++;
            if (rd.nextInt(count) == 0) result = i;
        }
        return result;
    }
}



Version #1 Naiive
4.42 %
class Solution {

    Map<Integer, List<Integer>> map = new HashMap<>();
    Random rd;
    public Solution(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], new ArrayList<>());
            }
            map.get(nums[i]).add(i);
        }
        rd = new Random();
    }
 
    public int pick(int target) {
        List<Integer> index = map.get(target);
        return index.get(rd.nextInt(index.size()));
    }
}