1、前言

2、思路

这道题简单的思路是定义一个 Map<Integer, List<Integer>> 的结构的数据，然后把数往里塞就行。

最吊的方法是蓄水池抽样。核心思想是，你前进到 k，0～k 中每个数被选中的概率为 1/k；那么如果到 n，0～n 中每个数被选中的概率为 1/n。也就是说，到了最后的一个数 n，我们以 1/n 的概率能得到某个数。

3、代码

简单方法：

class Solution {

    private Map<Integer, List<Integer>> map = new HashMap<>();

    public Solution(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            this.map.putIfAbsent(nums[i], new ArrayList<>());
            this.map.get(nums[i]).add(i);
        }
    }
    
    public int pick(int target) {
        List<Integer> list = this.map.get(target);
        return list.get((int)(Math.random() * list.size()));
    }
}

蓄水池抽样：

class Solution {

    private Random random;
    private int[] nums;

    public Solution(int[] nums) {
        this.nums = nums;
        this.random = new Random();
    }
    
    public int pick(int target) {
        int ans = 0;
        for(int i = 0, count = 0; i < nums.length; i++){
            if(nums[i] == target){
                count++;
                if(random.nextInt(count) == 0){
                    ans = i;
                }
            }
        }
        return ans;
    }
}