Force deduction solution summary 398 random number index

Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

Given an array of integers that may contain repeating elements , The index of a given number is required to be output randomly . You can assume that a given number must exist in an array .

Be careful ：
The array size can be very large . Solutions that use too much extra space will not pass the test .

Example :

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

// pick(3) The index should be returned 2,3 perhaps 4. The return probability of each index should be equal .
solution.pick(3);

// pick(1) Should return to 0. Because only nums[0] be equal to 1.
solution.pick(1);

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/random-pick-index
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  use map Of key Load each value ,value For its index Collection of values .
* pick when , take List Then take the value randomly .

Code ：

public class Solution398 {

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

    public Solution398(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> integers = map.get(target);
        int index = random.nextInt(integers.size());
        return integers.get(index);
    }
}