# Question

Formatted question description: https://leetcode.ca/all/398.html

 398	Random Pick Index

Given an array of integers with possible duplicates,
randomly output the index of a given target number.

You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

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

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums is equal to 1.
solution.pick(1);



# Algorithm

Define two variables, counter cnt and return result res.

Traverse the entire array,

• If the value of the array is not equal to target, skip directly;
• If it is equal to target, the counter is increased by 1,

Then we randomly generate a number in the range of [0,cnt). If this number is 0, we assign res.

Java