https://www.cnblogs.com/snowInPluto/p/5996269.html
class Solution {
public:
vector<int> nums;
Solution(vector<int>& nums) {
this->nums=nums;
}
int pick(int target) {
int flag=1;//是否第一个满足要求的
int res;
int ind=-1;
int cnt=1;//等于target的数的 个数
for(auto c:nums){
ind++;
if(flag==1){//第一个满足要求的数的 ind 赋值给 res
if(c==target){
res=ind;
flag=0;
}
continue;
}
//第二个及之后等于target的元素是否被选择的概率p=1/(cnt+1)，至于为什么是这样，看链接
if(c==target){
if((rand()%(cnt+1))==cnt){
res=ind;
}
cnt++;
}
}
return res;
}
};
