水池抽样题目

水池抽样题目

Tans 1,534 2022-04-25

水池抽样题目通常来说就是让我们返回一个随机数,保证每个数的概率都为1k\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);

这一道题可以是用哈希表水池抽样两种解法。这里着重介绍一下水池抽样。
假设我们需要取出值为targettarget的随机下标, 设最终取出的下标为targetIdxtargetIdx,那么也就是意味着下标在targetIdxtargetIdx之后的值为targettarget的值都没有取到,就有:
P(第 i 次遇到值为 target  的元素的下标成为最终返回值)=P(第 i 次随机选择的值=0)×\timesP(第 i+1 次随机选择的值 !=0)×\times×\timesP(第 k 次随机选择的值 !=0)
也就是:
P(i)=1i×(11i+1)×(11i+2)×....×(11k)=1kP(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;
    }
};