共计 1675 个字符，预计需要花费 5 分钟才能阅读完成。
题目要求
Given an array of integers 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.
Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.
Example:
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);
// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);
设计一个数据结构，使得从该数据结构中查询一个数字时，能够以等概率返回该数字所在的任何下标。额外的要求是只要占用 O(1) 的额外的空间复杂度。
思路一：O(2n) 的实现
其实要是想在 O(1) 的时间内完成随机数的获取，只需要缓存每个数字出现的下标，但是这意味着需要先对数据进行遍历，并且还需要 O(n) 的空间来额外存储数字下标的集合。这违背了题目意思。所以我们只能每次在获取数字的时候来统计数字出现的次数，然后针对次数获取随机数下标。
代码如下：
private int[] nums;
private Random r;
public Solution(int[] nums) {
this.nums = nums;
this.r = new Random();
}
public int pick(int target) {
int count = 0;
int result = -1;
for(int i = 0 ; i<nums.length ; i++) {
if(target == nums[i]) {
count++;
}
}
int index = r.nextInt(count);
for(int i = 0 ; i<nums.length ; i++) {
if(target == nums[i]) {
index–;
if(index == -1){
result = i;
break;
}
}
}
return result;
}
思路二：蓄水池问题
有没有可能在一次的遍历中，找到这个随机下标呢？这就涉及到一个概率问题，即当我在遍历过程中遇到这个数字时，我是否需要选择它作为我的结果值。
首先介绍一下蓄水池抽样算法。蓄水池抽样算法主要对应的是这样的一个问题，假设有一个非常大的数据集，或者是一个以流的形式作为输入的数据集，希望从中选择 K 个样本，此时我们可能无法把所有的样本都放在内存中，因此只能保存一个大小为 K 的集合，每次遇到一个数据时，决定是否将其放入样本中。
因此，假设当前遇到的数据总共有 N 个，如果 N 小于 K，则每个数据被选中的概率为 1，如果 N >K，则每个数据被选中的概率为 K /N，旧样本中数据被保留的概率为 1 – K(N-K)/ N 即 K /N，因此每一个旧的数据被替换掉的概率为 1 /N。
按照这个思路，我们在下面的遍历时，每遇到一个新元素，就判断当前选中的元素是否会被该元素替换掉即可。
private int[] nums;
private Random r;
public Solution(int[] nums) {
this.nums = nums;
this.r = new Random();
}
public int pick(int target) {
int count = 0;
int result = -1;
for(int i = 0 ; i<nums.length ; i++) {
if(nums[i] == target) {
int index = r.nextInt(++count);
if(index == 0) {
result = i;
}
}
}
return result;
}
