以在线的方式从一个数据流中随机选出k个元素，注意点：

  1. 数据流长度未知，可能很大，所以不能先遍历保存成数组再取随机下标。
  2. 在线处理，边读取边计算结果。
  3. 不管数据规模有多大，取出的k个元素概率一样的，都是k/N，N是总长度。

蓄水池抽样的典型应用场景如下：

  1. 给定一个长度未知的单链表，请随机选择链表的一个节点，并返回相应的节点值。 要求每个节点被选中的概率都是一样的。
  2. 同上，但要求随机选出m个结点，同样要求每个节点被选中的概率都一样。


解决方法：

先以随机选出1个结点为例，第一次抽样时，选中该结点的概率为1，第二次抽样时，有1/2的概率将第二次抽样的值作为选中的结点，第三次抽样时，选中的概率为1/3，以此类推，遍历完所有的结点，最后保留的结点就是符合要求的随机结点，以单链表为例，示例代码如下：

int getRandom(ListNode *head) {
    int ans;
    int i = 1;
    for(auto node = head; node != nullptr; node = node->next) {
        if(rand() % i == 0) { // 第i个结点选中的概率为1/i，如果命中
            ans = node->val;
        }
        i++;
    }
    return ans;
}


接下来是随机选取m个结点，算法思路如下：

  1. 如果接收数据量小于m，则依次放入蓄水池。
  2. 当接收到第i个数据，且i>=m时，在[0, i]范围内随机选取数d，如果d落在[0, m-1]范围内，则用收到的数替换蓄水池中的第d个数据。

示例代码如下：

vector<int> getRandom(ListNode *node, int m) {
    vector<int> pool(m);
    int i = 0;
    while(i < m && node != nullptr) {
        pool[i] = node->val;
        node = node->next;
        i++;
    }

    while(node != nullptr) {
        int d = rand() % (i+1); // 随机获得一个[0,i]内的整数
        if(d < m) { // 如果整数落在[0,m-1]范围内，则替换蓄水池中的元素
            pool[d] = node->val;
        }
        node = node->next;
		i++;
    }

    return pool;
}


蓄水池抽样示例：



  • 无标签