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 arraynums.int pick(int target)Picks a random indexifromnumswherenums[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 - 1targetis an integer fromnums.- At most
104calls will be made topick.
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);
}
Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[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;
};
Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[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;
}
}
Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[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)];
};
Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[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):
self.indexes[num].add(i)
def pick(self, target):
return random.sample(self.indexes[target], 1)[0]
Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]