Resevior Sampling蓄水池算法java实现 | CodeInterviews
Randomly return the index of maximal elements in the array.
follow up: 要求linear time 和constant space
先把前k个数放入蓄水池，对第k+1，我们以k/(k+1)概率决定是否要把它换入蓄水池，换入时随机的选取一个作为替换项，这样一直做下去，对于任意的样本空间n，对每个数的选取概率都为k/n。也就是说对每个数选取概率相等。
- Create an array reservoir[0..k-1] and copy first k items of stream[] to it.
- Now one by one consider all items from (k+1)th item to nth item.
- Generate a random number from 0 to i where i is index of current item in stream[]. Let the generated random number is j.
- If j is in range 0 to k-1, replace reservoir[j] with arr[i]
Read full article from Resevior Sampling蓄水池算法java实现 | CodeInterviews
No comments:
Post a Comment