# 398. Random Pick Index (Medium)

https://leetcode.com/problems/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);
```

## Solutions

• Java

https://www.cnblogs.com/grandyang/p/5875509.html

``````class Solution {

private int[] nums;

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

public int pick(int target) {
int count = 0;
for (int num : nums) {
if (num == target) {
count++;
}
}

int pick = (int)(Math.random()*count);

int idx = 0;
count = 0;
for(int i = 0; i < nums.length; i ++){
if(nums[i] != target) continue;

if (count++ == pick) {
idx = i;
break;
}
}

return idx;
}
}
``````