等概率抽样——水塘抽样
给出一个数据流,这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次,且不能使用额外的空间,请写出一个随机选择算法,使得数据流中所有数据被选中的概率相等。
从头开始遍历数据,当遍历到第n个数据时,从0到n-1中随机选取一个数字,如果选到数字0,则将答案置为该数据的值,否则答案不变继续向下抽样,遍历完所有数据后,抽到每个数据的概率都是
1
n
\frac {1}{n}
n1
证明:
P(第i个数据为最终答案)
=P(第i个数据抽到随机数0)×P(第i+1个数据没有抽到随机数0)×P(第i+2个数据没有抽到随机数0)×···×P(第n个数据没有抽到随机数0)
=
1
i
\frac {1}{i}
i1×(1-
1
i
+
1
\frac {1}{i+1}
i+11)×(1-
1
i
+
2
\frac {1}{i+2}
i+21)×···×(1-
1
n
\frac {1}{n}
n1)
=
1
i
\frac {1}{i}
i1×
i
i
+
1
\frac {i}{i+1}
i+1i×
i
+
1
i
+
2
\frac {i+1}{i+2}
i+2i+1×···×
n
−
1
n
\frac {n-1}{n}
nn−1
=
1
n
\frac {1}{n}
n1
例题
LeetCode382. 链表随机节点
给你一个单链表,随机选择链表的一个节点,并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution 类:
Solution(ListNode head) 使用整数数组初始化对象。
int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
class Solution
{
public:
ListNode *head;
Solution(ListNode *head)
{
this->head = head;
}
int getRandom()
{
int ret = 0;
int i = 1;
ListNode *node = head;
while (node)
{
int t = rand() % i;
if (t == 0)
{
ret = node->val;
}
node = node->next;
i++;
}
return ret;
}
};