leetCode-398:Random Pick Index

问题描述

给定一个数组，要求随机输出给定的目标数字 target 的索引。题目链接：点我

样例输入输出

输入：

[“Solution”, “pick”, “pick”, “pick”]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]

输出：
[null, 4, 0, 2]

解释：

Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

输入：

[“Solution”, “pick”]

[[[1, 2, 3]], [1]]

输出：

[null, 0]

问题解法

初始化时先遍历数组，将相同数字的下标存在 map 中，后续取数字时取出对应数字的下标列表，从中随机取出下标返回。代码如下

class Solution {

    private Map<Integer, List<Integer>> map = new HashMap<>();
        
    private Random random = new Random();
    
    public Solution(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            List<Integer> temp = map.getOrDefault(nums[i], new ArrayList<>());
            temp.add(i);
            map.put(nums[i], temp);
        }
    }

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