题目内容

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意：
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例:

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);

解题思路

创建一个Map，key是数组的元素，value是一个List，存放对应元素索引，获取时通过数值从Map中get到对应索引的List，然后随机返回一个List中的元素。

public class Solution {

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

    public Solution(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            List<Integer> list = map.get(nums[i]);
            if (list == null) {
                list = new ArrayList<>();
                map.put(nums[i], list);
            }
            list.add(i);
        }
    }

    public int pick(int target) {
        List<Integer> list = map.get(target);
        return list.get((int) (Math.random() * list.size()));
    }
}

运行结果

拓展学习

看题解学习到了一种新的方法，叫蓄水池抽样算法，可以用来处理不定长数据流的问题。
思路：
假设在数组nums中有m个值为target的数，答案需要在m个数中随机返回一个数的索引，且每个索引返回的概率相同。首先遍历数组，当遇到第一个与target相同的元素时，先设定这个元素的索引为答案，继续往后遍历，每当遇到第n个与target相同的元素时，就在[ 0 - n )之间取随机数，如果结果为0，则更新当前元素索引为答案。最后返回答案。

class Solution {

    int[] nums;
    public Solution(int[] nums) {
        this.nums = nums;
    }

    public int pick(int target) {
        int count = 0;
        int idx = 0;
        for(int i = 0; i < nums.length; i++){
            if (nums[i] == target) {
                count++;
                if((int) (Math.random() * count) == 0){
                    idx = i;
                }
            }
        }
        return idx;
    }
}

运行结果