如何在无限序列中随机抽取元素 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何在无限序列中随机抽取元素

评论礼仪 见这里，违者直接拉黑。

[GBWen]

请问下思考2 randomGet 有文章吗

[LBingXiang]

参考382. 链表随机节点和东哥的思路，写了下398. 随机数索引的java代码

思路还是和前一个题一样，因为数组可能很大，我们就把nums[k] == target的每一个当做链表的节点即可，而下标就是val

class Solution {

    int[] nums;
    Random r = new Random();
    public Solution(int[] nums) {
        this.nums = nums;
    }
    
    public int pick(int target) {
        int i = 0, res = 0;
        for (int k = 0; k < nums.length; k++) {
            if (nums[k] == target) {
                i++;
                if (0 == r.nextInt(i)) {
                    res = k;
                }
            }
        }
        return res;
    }
}

[zyxing-Andrew]

有点疑惑的是，对于使用nextInt(i)在遍历一遍的情况下随机选取数据这个过程，是如何保证一定能满足if语句的呢（即如何保证一定可以获得一个答案值）？为什么不会出现遍历一遍res没有被赋值的情况

[victory460]

这个问题的难点在于，随机选择是「动态」的，比如说你现在你有 5 个元素，你已经随机选取了其中的某个元素 a 作为结果，但是现在再给你一个新元素 b，你应该留着 a 还是将 b 作为结果呢，以什么逻辑选择 a 和 b 呢?

这个问题，本文感觉还是没解释清楚哇？为什么要选择b呢？

[victory460]

有点疑惑的是，对于使用nextInt(i)在遍历一遍的情况下随机选取数据这个过程，是如何保证一定能满足if语句的呢（即如何保证一定可以获得一个答案值）？为什么不会出现遍历一遍res没有被赋值的情况

我也有同样的疑惑：如何保证一定可以获得一个答案值？为什么不会出现遍历一遍res没有被赋值的情况？

[labuladong]

@victory460 @zyxing-Andrew 在循环第一次执行的时候，randInt(1) 生成的数一定是 0，所以相当于 res 被初始化为 0 了。

[huanghao7414]

这道题目我觉得困惑的点在于，为什么不被替换的概率是 1-1/(i+1);其实可以这样想，保持原来的选择，这个选择的是哪个我们不清楚，但是从概率学上说应该是有i种可能，每种可能的概率为1/(i+1)，所以得到：i/(i+1)。

[zhanglei-underdog]

东哥，在随机抽取k个元素时，在程序里能不能初始化 int i=k -1 ;
// 生成一个 [0, i) 之间的整数
int j = r.nextInt(++i);
这样第一次选中的概率就为1

如果不可以，那么是不是意味着解决只抽取一个元素的问题， 需要初始化 int i=1;

[LebronHarden1]

理解了,但是写到力扣上不对是怎么回事

[LebronHarden1]

少了一个this,可以这样理解,第一题前i-1个元素爱咋更新咋更新res,但是第i个元素把res定死之后,从i+1一直到n都处于不更新res的概率,把它们相乘就是证明的那个图

[lhcezx]

写了个C++版本的，力扣居然超时了，没搞懂为啥会超时

class Solution {
    vector<int> nums;
public:
    Solution(vector<int>& nums) {
        this->nums.assign(nums.begin(), nums.end());
    }
    
    int pick(int target) {
        int counter = 0;
        int res = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != target) continue; 
            counter++;
            if (rand() % counter == 0) res = i;
        }
        return res;
    }
};