以在线处理的方式从一个长度未知的数据流中随机选出k个元素,注意点:以在线的方式从一个数据流中随机选出k个元素,注意点:
- 数据流长度未知,可能很大,所以不能先遍历保存成数组再取随机下标。
- 在线处理,边读取边计算结果。不管数据规模有多大,取出的k个元素概率一样的。
- 不管数据规模有多大,取出的k个元素概率一样的,都是k/N,N是总长度。
蓄水池抽样的典型应用场景如下:
- 给定一个长度未知的单链表,请随机选择链表的一个节点,并返回相应的节点值。 要求每个节点被选中的概率都是一样的。
- 同上,但要求随机选出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; } |
接下来是随机选取m个结点,算法思路如下:
- 如果接收数据量小于m,则依次放入蓄水池。
- 当接收到第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; } |
蓄水池抽样示例: