水池抽样题目通常来说就是让我们返回一个随机数，保证每个数的概率都为$\frac{1}{k}$，下面分享几道题目供大家参考。

398. 随机数索引

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
样例：
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);
// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);

这一道题可以是用哈希表和水池抽样两种解法。这里着重介绍一下水池抽样。
假设我们需要取出值为$target$的随机下标, 设最终取出的下标为$targetIdx$，那么也就是意味着下标在$targetIdx$之后的值为$target$的值都没有取到，就有：
P(第 i 次遇到值为 target  的元素的下标成为最终返回值)=P(第 i 次随机选择的值=0)$\times$P(第 i+1 次随机选择的值 !=0)$\times$⋯$\times$P(第 k 次随机选择的值 !=0)
也就是：
$P(i)=\frac{1}{i}\times(1-\frac{1}{i+1})\times(1-\frac{1}{i+2})\times....\times(1-\frac{1}{k}) =\frac{1}{k}$

所以这样的随机抽样满足条件。

class Solution {
public:
    vector<int> &nums;
    Solution(vector<int>& nums): nums(nums){}
    
    int pick(int target) {
        int ans = 0, cnt = 0;
        int len = nums.size();
        for(int i = 0; i < len; i++){
            if(nums[i] == target){
                cnt++;
                if(rand() % cnt == 0){
                    ans = i;
                }
            }
        }
        return ans;
    }
};