## Algorithm

Problem Name: 398. Random Pick Index

Given an integer array `nums` 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.

Implement the `Solution` class:

• `Solution(int[] nums)` Initializes the object with the array `nums`.
• `int pick(int target)` Picks a random index `i` from `nums` where `nums[i] == target`. If there are multiple valid i's, then each index should have an equal probability of returning.

Example 1:

```Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

Explanation
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.
```

Constraints:

• `1 <= nums.length <= 2 * 104`
• `-231 <= nums[i] <= 231 - 1`
• `target` is an integer from `nums`.
• At most `104` calls will be made to `pick`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int *nums;
int sz;
} Solution;
​
Solution* solutionCreate(int* nums, int numsSize) {
Solution *obj = malloc(sizeof(Solution));
//assert(obj);
obj->nums = nums;
obj->sz = numsSize;
return obj;
}
​
int solutionPick(Solution* obj, int target) {
int i, r, n, k;
k = -1;
n = 1;
r = random();
for (i = 0; i  <  obj->sz; i ++) {
if (obj->nums[i] == target) {
if (!(r % n)) {
k = i;
}
n ++;
}
}
return k;
}
​
void solutionFree(Solution* obj) {
free(obj);
}
``````
Copy The Code &

Input

cmd
["Solution", "pick", "pick", "pick"] [[[1, 2, 3, 3, 3]], [3], [1], [3]]

Output

cmd
[null, 4, 0, 2]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
Solution(vector<int> nums) {
this->nums = nums;
}

int pick(int target) {
int res = -1, count = 0;
for(int i = 0; i  <  nums.size(); i++){
if(nums[i] != target) continue;
if(res == -1) res = i, count++;
else{
count++;
if(rand() % count == 0) res = i;
}
}
return res;
}

private:
vector<int>nums;
};
``````
Copy The Code &

Input

cmd
["Solution", "pick", "pick", "pick"] [[[1, 2, 3, 3, 3]], [3], [1], [3]]

Output

cmd
[null, 4, 0, 2]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
int[] nums;
Random rand;
public Solution(int[] nums) {
this.nums = nums;
rand = new Random();
}

public int pick(int target) {
int count = 0;
int res = 0;
for (int i = 0; i  <  nums.length; i++) {
if (nums[i] == target) {
if (rand.nextInt(++count) == 0) {
res = i;
}
}
}
return res;
}
}
``````
Copy The Code &

Input

cmd
["Solution", "pick", "pick", "pick"] [[[1, 2, 3, 3, 3]], [3], [1], [3]]

Output

cmd
[null, 4, 0, 2]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const Solution = function(nums) {
this.nums = nums;
};

Solution.prototype.pick = function(target) {
const res = [];
for (let i = 0; i  <  this.nums.length; i++) {
if (this.nums[i] === target) {
res.push(i);
}
}
return res[Math.floor(Math.random() * res.length)];
};
``````
Copy The Code &

Input

cmd
["Solution", "pick", "pick", "pick"] [[[1, 2, 3, 3, 3]], [3], [1], [3]]

Output

cmd
[null, 4, 0, 2]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:

def __init__(self, nums):
self.indexes = collections.defaultdict(set)
for i, num in enumerate(nums):

def pick(self, target):
return random.sample(self.indexes[target], 1)[0]
``````
Copy The Code &

Input

cmd
["Solution", "pick", "pick", "pick"] [[[1, 2, 3, 3, 3]], [3], [1], [3]]

Output

cmd
[null, 4, 0, 2]