class Solution {
vector<int> nums;
public:
Solution(vector<int> nums) {
this>nums = nums;
srand(time(NULL));
}
int pick(int target) {
int cnt = 0;
int index = 1;
for(int i = 0; i<nums.size(); i++) {
if (nums[i] == target) {
cnt++;
if (index == 1)
index = i;
else {
if(rand()%cnt == 0)
index = i;
}
}
}
return index;
}
};
C++ O(n) solution


@fittaoee check out reservoir sampling. (https://en.wikipedia.org/wiki/Reservoir_sampling)

said in C++ O(n) solution:
if (index == 1)
index = i;
else {you don't need the if(index==1) statement. the first number equal to target will always be selected.