398. 随机数索引

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

注意：
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);

// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);

思路一（暴力）：

class Solution {
    Map<Integer, List<Integer>> map = new HashMap<>();

    public Solution(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])){
                List<Integer> tmp = map.get(nums[i]);
                tmp.add(i);
            }else{
                List<Integer> array = new ArrayList<>();
                array.add(i);
                map.put(nums[i], array);
            }
        }
    }
    
    public int pick(int target) {
        List<Integer> tmpArray = map.get(target);
        int n = tmpArray.size();
        Random random = new Random();
        int idx = random.nextInt(n); //从List中随机获取值
        return tmpArray.get(idx);
    }
}

思路二（蓄水池抽样算法）：

　　• 随机算法之 — "蓄水池抽样算法" 。
　　• 分析有三个数据的数据流的情况。为了方便，我们按顺序给流中的数据命名为1、2、3。我们陆续收到了数据1、2和前面的例子一样，我们只能保存一个数据，所以必须淘汰 1 和 2 中的一个。应该如何淘汰呢？不妨和上面例子一样，我们按照二分之一的概率淘汰一个，例如我们淘汰了 2。继续读取流中的数据 3，发现数据流结束了，我们知道在长度为 3 的数据流中，如果返回数据 3 的概率为 1/3，那么才有可能保证选择的正确性。也就是说，目前我们手里有 1 , 3 两个数据，我们通过一次随机选择，以 1/3 的概率留下数据 3，以 2/3 的概率留下数据 1。那么数据 1 被最终留下的概率是多少呢？
　　• 数据 1 被留下：（1/2).(2/3) = 1/3
　　• 数据 2 被留下概率：（1/2).(2/3) = 1/3
　　• 数据 3 被留下概率：1/3
　　• 这个方法可以满足题目要求，所有数据被留下返回的概率一样！
　　• 假设当前正要读取第 n 个数据，则我们以 1/n 的概率留下该数据，否则留下前 n-1 个数据中的一个。

class Solution {
    int[] nums;

    public Solution(int[] nums) {
        this.nums = nums;
    }
    
    public int pick(int target) {
        Random random = new Random();
        int idx = 0, n = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == target){
                n++; //蓄水池个数 + 1
                if(random.nextInt(n) == 0) idx = i; //n 个数随机取一个 == 0，就是 1/n 的概率
            }
        }
        return idx;
    }
}