页面历史记录

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

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

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

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

...

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

...