看看下面两道题，它的解答非常简单，即使没学过信息学的人也可以想到答案。你能在多短的时间内想出问题的算法来？一小时？一分钟？一秒钟？
1. 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
2. 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*…*A[n]/A[i]。你不能使用除法运算。
Solution:
1. 遍历链表，给每个元素赋一个0到1之间的随机数作为权重（像Treap一样），最后取出权重最大的k个元素。你可以用一个堆来维护当前最大的k个数。
2. 从前往后扫一遍，然后从后往前再扫一遍。也就是说，线性时间构造两个新数组，P[i]=A[1]*A[2]*…*A[i]，Q[i]=A[n]*A[n-1]*…*A[i]。于是，B[i]=P[i-1]*Q[i+1]。
突然想到，给别人(MM?)介绍信息学时，用这两道题当例子挺合适的。
决定把你的空间的东西看完 提高智商
顶*…*乘法*…*有趣
看不懂……[muteness]
Er,发现答案了……现在看懂了[redface]
第2个不错~
第二个简单
第二个悲哀地没想到,第一个就更别说了
第三个问题：为什么介绍给mm好？
第一个是什么思路呢？
赞，很好
第二题… 我曾经自己想到过这题.. 但没想到解法..
看到了解析，（-_-#隐藏的真好），第二题方法很经典。
第一题要是先遍历一遍链表，将每个元素存储在另一个数组中，再random不行？好像只规定了链表只能遍历一次，而没有规定另一个数组不行，虽然有点投机取巧，但绝对符合要求(一次and随机)。^_*
回复：现在我又加了一个条件，n很大，嘻嘻
不错…
第一题。。。。不过用random算（1到n）中的随机数。。然后再算（1到n-1）随机数。。直到算（1到n-k）随机数。。。排序。。。历遍。。。能成吧。。
第二题。。想不到。。
不行应为事先不知道N是多少
i属于（0，n）的时候，楼主的解法才正确，否则i=n的时候，ms会溢出
B[1] = Q[2]
B[n] = P[n – 1]
B[i] = P[i – 1] * P [i + 1] (2 <= i <= n – 1)
这样就不会溢出了
汗…第二题也太简单了
第二题只会用两重循环做。
错了，是两个一重循环。
第二题
a[1]*a[2]*…*a[n]*exp(-ln(a[i]));
猥琐的减法
堆的维护还需要付出log(n)的时间，不是一个简明的做法。
不失一般性，令K=1。
算法：从头开始遍历链表。对于第i个节点，在1/i的概率下，让这个节点成为候选节点。最后留下个那个候选节点则是概率为1/N的幸运儿。
用数学归纳法证明: 任何一个节点的入选概率都是1/N。
N = 1时自然正确。
假设N=i时，每个节点的入选概率都是1/i。也就是说，当前候选节点可能是1..i中的任何一个。
则当N=i+1时，当前候选节点继续保留的概率为(1 – 1/(i+1))。它的总入选概率是1/i * (1 – (1/(i+1)) =
1/(i+1)。 而第i+1个节点的入选概率是1/(i+1)。
因此，当N=i+1时，每个节点的入选概率是1/(i+1)。
(证毕)
当K>1时，令候选节点集合大小为k。当要替换候选节点时，每次从中这个集合中随机替换即可。
1000 字 限制 不合理，想帖程序都不成
第1题我想到的方法和20楼的huazz类似。
20楼，这儿堆的维护是log(7)不是log(N)，所以楼主答案确是精简的。
20楼的算法如何推广到K>1的情况，楼主帮忙说明一下
20楼的算法如何推广到K>1的情况：
维护大小为K的集合，每个节点留下的概率变为k/i
在N＝i时， 每个节点在集合中的概率都为k/i
N=i+1时 前i个节点中任一个仍然在集合中的概率为：
k/i * ( 1-k/(i+1) + k/(i+1)*(k-1)/k ) ＝ k/(i+1)
其中1-k/(i+1)是第i＋1个节点未被选中的概率，k/(i+1)*(k-1)/k是第i＋1个点被选中了，但在集合中没有被其替换的概率。
很有趣啊
我在ipad上，全选也没有反色的。。。。
第二题无耻的用消因子做…
第一题先取k个之后的random 0，1 换与不换 random 0,k 换已有的元素可以否。。。
为什么2的答案里 构造两个新数组，P[i]=A[1]*A[2]*…*A[i]，Q[i]=A[n]*A[n-1]*…*A[i]的复杂度是O(n)?
回31L：
应该是两个不重叠的for循环吧~O(n)+O(n)=O(n)
第一题非常简单，M牛的答案其实有点儿杀鸡用牛刀了，而且时间复杂度略高（遍历的同时维护大小为k的堆，总共需要O(N * log k)的时间）。有兴趣的可以看一下我前些日子写的博客：单次遍历，等概率随机选取问题（http://www.gocalf.com/blog/random-selection.html），遍历链表一次，O(N)时间，O(k)辅助空间（与25楼方法差不多）。另外还有两篇文章是关于带权选取的，也就是每个元素都有一个权重，要求还是单次遍历但元素被取出的概率与其权重相关。带权的时候，k=1还可以用同样的方法去做，k>1的时候就用到了M牛答案中方法的扩展，有兴趣可以在我博客里找一下，我给出了概率理论值和对算法的证明。
很喜欢你的博客
a[2]*a[3]*a[4]
a[1] a[3]*a[4]
a[1]*a[2] *a[4]
a[1]*a[2]*a[3]
这样行吗
问题2想了好久啊，居然可以用对数化将乘法化加法，2n的复杂度就OK，哎，想了快一个小时，看来我这智商有点堪舆。。
问题1比较幸运，1分钟吧：初始设置取数间隔t=1，如果取到了k个到数组K，还没结束即N>t*k,则设置间隔t++,数组K是可以反复遍历修改的。直到t*k>N，此时取到的前t1(t1*k刚>N)个数是在前（t1-1）*k中等间隔取得，之后的数是按照上一次的间隔(t-1)取得的。
问题二，复杂度无需2n，n就足够，只是在循环中做两个计算操作即可。
牛B呀、、、
大家好，大家看来都忘了概率论的基本知识了。关于第一题，大家普遍认为，链表中任何一个元素被选中的概率是1/2 或者 1/N。你们错了。链表中一个元素出现在结果中的概率应该是 A(k,N-1)/A(k,N) 或者 C(k,N-1)/C(k,N)。A代表排列，C代表组合，在这里用哪个都有可能（但是更加可能是A)。至于为什么，你们自己想想吧。你们可以算算这两个式子，结果既不是1/2也不是1/N。有意见请给我发邮件ethanchung100@gmail.com
我是楼上的，不好意思刚才的式子少打了一部分：
“链表中一个元素出现在结果中的概率应该是 (k+1)*A(k,N-1)/A(k,N)”
化简后得到链表中一个元素出现在结果中的概率：
(k+1)/(n-k+1)
第一题概率不对。每一个元素都应该有k/N的概率被选中，博主的办法没法保证每一个元素都有k/N的概率成为最大的k个。我觉得这道题愿意付出存储代价的话，准备一个(0,1)均匀分布的随机数骰子，投出来a1,a2,a3….ak k个数，然后分别选择第floor(a1*N)个元素，第floor(a2(N-1))个元素，第floor(a3(N-2)个元素，….，第floor(ak(N-k+1))个元素，即可。选择到的元素必须要移除。
第一题比较完的时候，去元素的时候不是要重现遍历链表吗？而题目不是说只能遍历一次吗？