Dare2Solve
Given an array of integers, we need to pick an index at random from the array where a given target number appears. The key challenge is to ensure each target number is picked with equal probability, even when the target appears multiple times in the array.
To ensure equal probability of picking any occurrence of the target, we can use a reservoir sampling technique. As we iterate over the array and encounter each instance of the target, we randomly decide whether to select this index, progressively reducing the likelihood as more instances are encountered.
res
as -1 and a count
to keep track of how many times the target has been seen.1/count
.res
to the current index.O(n)
, where n
is the number of elements in the array.
O(1)
, excluding the input array, as only a few extra variables are used.
class Solution {
public:
vector<int> nums;
Solution(vector<int>& nums) {
this->nums = nums;
}
int pick(int target) {
int res = -1;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == target) {
count++;
if (rand() % count == 0) {
res = i;
}
}
}
return res;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* int param_1 = obj->pick(target);
*/
class Solution:
def __init__(self, nums: list[int]):
self.nums = nums
def pick(self, target: int) -> int:
res = -1
count = 0
for i, num in enumerate(self.nums):
if num == target:
count += 1
if random.randint(0, count - 1) == 0:
res = i
return res
class Solution {
private int[] nums;
private Random random;
public Solution(int[] nums) {
this.nums = nums;
this.random = new Random();
}
public int pick(int target) {
int res = -1;
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
count++;
if (random.nextInt(count) == 0) {
res = i;
}
}
}
return res;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int param_1 = obj.pick(target);
*/
var Solution = function(nums) {
this.num = nums;
};
/**
* @param {number} target
* @return {number}
*/
Solution.prototype.pick = function(target) {
let res = -1, count = 0;
for(let i = 0; i < this.num.length; i++) {
if(this.num[i] === target) {
count++;
if(Math.floor(Math.random() * count) === 0) {
res = i;
}
}
}
return res;
};