1.蓄水池抽样问题

'''经典面试题分析:蓄水池抽样.题目:要求从N个元素中随机的抽取k个元素，其中N无法确定。只能扫描一次数据''''''分析:1.如果题目的N给定了,那么算法是把1到N这些整数shuffle一下,  然后按照这个index取前k个即可.效率是O(N**2)的.但是由于只读取了k次数据.  当读取数据一次很慢时候,这个效率可以.2.回归这个题目,他要求N无法确定.  只需要:  1.把前k个数按顺序放一个数组里面.  2.对于第k+1个数.randint(1,k+1)如果rand出来的数在(1,k)里面,那么k+1位置的数与    数组中rand出来的这个index的数交换.  3.后面类似.对于第k+i个数就randint(1,k+i)............  所以:一共randint跑了N次.数据也只扫描了一次.'''import randomdef savirior_sampling(data,k):#从data里面抽样k个元素,data这里用数组来模拟    output=data[:k]    #模拟不知道数组的长度所以用try来做    index=k    while 1:                try:                                  obj=random.randint(0,index)            if obj