题目:有一个网页抓取器每秒钟抓取一个网页,定义一个API,每次调用的时候要等概率的从目前已经抓取的网页中随机选取一个,应该怎么实现? 分析:这题题目定义有一定迷惑性,最直接的思路貌似应该是先保存当前采集到的所有网页,然后随机采样,这显然不是这题的考点。这题想只用O(1)的空间。其实就等价于有一个很长的数据流,数据量大到无法载入内存,怎么做随机等概率采样?容易想到的思路是产生一个0到1之间的随机数,然后根据目前数据长度乘以随机数构成index取数,时间复杂度O(1),但是需要额外O(n)存储空间,不符合要求。用bit…

2015年2月24日 0条评论 1点热度 阅读全文