对于数据流中的数据，我们将其存储到容器中，并使用随机数取出[0, n)的任意一个元素，完成等概率抽样。
该算法的时间与空间复杂度均为O(n)。
水塘抽样算法用于：在数据流中以O(n)的时间复杂度和O(1)的空间复杂度完成等概率抽样。
对于数据流中的第i个数，它有 1/i 的概率被替换为本轮随机抽样的结果：
int ans = 0;
for (int i = 1; i <= n; ++i)
{
if (rand() % i == 0) // 1/i的概率
ans = array[i];
}
return ans;
水塘抽样的算法实现也非常简单，现在给出其证明过程：
假设第i个值被抽取，则[i+1, n]都没有被抽取，即：
P
(
第
i
个被抽取
)
=
1
/
i
∗
P
(
第
i
+
1
个没被抽取
)
∗
.
.
.
∗
P
(
第
n
个没被抽取
)
=
1
/
i
∗
i
/
(
i
+
1
)
∗
(
i
+
1
)
/
(
i
+
2
)
∗
.
.
.
∗
(
n
−
1
)
/
n
=
1
/
n