题目链接：随机数索引
题目描述：
给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。
实现 Solution 类：
Solution(int[] nums) 用数组 nums 初始化对象。
int pick(int target) 从 nums 中选出一个满足 nums[i] == target 的随机索引 i 。如果存在多个有效的索引，则每个索引的返回概率应当相等。
方法一：
1）初始化时，将nums赋值给另一个数组；时间O(1)
2）pick时，对数组进行遍历，使用reduce方法存储下所有和target相等的元素的索引，在得到的数组中使用Math.random()随机选择一个元素。时间O(n)，空间O(n)。
总时间O(mn)，m为pick次数，n为nums数组元素个数。空间O(n)，借助另一个数组。
js代码如下：
var Solution = function(nums) {
this.arr=nums;
};
/**
* @param {number} target
* @return {number}
*/
// 共n个数，这样对于每一个target的时间都是O(n)，那么m个target的时间就是O(mn)，需要优化
Solution.prototype.pick = function(target) {
let temp=this.arr.reduce((prev,cur,index)=>{
if(cur==target){
prev.push(index);
}
return prev;
},[])
let index=Math.floor(Math.random()*temp.length);
return temp[index];
};方法二：哈希表
1）在初始化的时候，将nums中的元素都存入一个哈希表中，key元素值，value是一个数组，保存着相等元素值的所有索引。时间O(n)，空间O(n)
2）pick时，直接从哈希表中取出对应数组，使用Math.random()取值即可。时间O(1)。
总时间O(n)，空间O(n)。
js代码如下：
var Solution = function(nums) {
this.map=new Map();
const length=nums.length;
for(let i=0;i<length;i++){
if(!this.map.has(nums[i]))
this.map.set(nums[i],[i]);
else{
this.map.set(nums[i],this.map.get(nums[i]).push(i));
}
}
};
// 时间复杂度O(1)，m个target对应的时间复杂度是O(m)，共O(m+n)约等于O(n)
Solution.prototype.pick = function(target) {
let temp=this.map.get(target);
let index=Math.floor(Math.random()*temp.length);
return temp[index];
};方法三：水塘取样
当nums的长度n确定时，其中的样本个数k也确定。从k个样本中随机选择一个，并且保证k个样本中每个样本被选中的概率都是1/k，直接使用Math.floor(Math.random()*k)即可。
但当数据量很大，nums的长度n不确定时，其中的样本个数k也不确定。就不能直接用上述公式，因为k是未知的。
但是，若共i个数据，每个数据被选择的概率都是1/i，不被选择的概率都是1-1/i，
那么k个样本中，最终样本i被选中的概率=第i个样本被选中的概率1/i * 第i+1个样本不被选中的概率1-1/(1+i)，，，*第k个样本不被选中的概率1-1/k，
化简得到P(i 被选中)=1/k，即每个样本被选中的概率都是1/k。这样是符合题目要求的。
显然，最终结论满足的充要条件是，当共i个数据时，每个数据被选中的概率是1/i，不被选中的概率是1-1/i。这一条件可以通过Math.floor(Math.random()*i)来实现。
由Math.floor(Math.random()*i)，可以得知[0,i)区间中每个数据被选中的概率都是1/i，
Math.floor(Math.random()*i)==0的概率为1/i
Math.floor(Math.random()*i)!=0的概率为1-1/i。
所以可以对每一个样本i，判断Math.floor(Math.random()*i)==0，若相等，概率为1/i，说明可以选中样本i，且概率为1/i。若不相等，概率为1-1/i，则说明i不能被选中。
最终留下的样本i的概率为1/i，其后面k-i个样本没被选中的概率都是1-1/(i+1),,,1-1/k
得到最后选择样本i的概率为：P(i被选中，i+1到k都没被选中)=1/i*i/(i+1)*(i+1)/(i+2)...*(k-1)/k=1/k。
js代码如下：
var Solution = function(nums) {
this.nums=nums;
};
// 时间复杂度O(n)，m个target对应的时间复杂度是O(m)，共O(mn)
Solution.prototype.pick = function(target) {
let ans=0;
// cnt统计样本数量
for(let i=0,cnt=0;i<this.nums.length;i++){
if(this.nums[i]==target){
cnt++;
if(Math.floor(Math.random()*cnt)==0)
ans=i;
}
}
return ans;
};用cnt来统计样本数量，当某个元素i是样本时，就判断Math.floor(Math.random()*cnt)==0，若相等，说明该样本可以被选中。不相等，说明不能。ans存储被选中的最后一个样本即可。
