2007-10-22 13:30| 
27 Comments | 本文内容遵从看看下面两道题，它的解答非常简单，即使没学过信息学的人也可以想到答案。你能在多短的时间内想出问题的算法来？一小时？一分钟？一秒钟？
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?)介绍信息学时，用这两道题当例子挺合适的。
27 条回复
您也随便说几句吧：
决定把你的空间的东西看完 提高智商
顶*...*乘法*...*有趣
看不懂……[muteness]
Er,发现答案了……现在看懂了[redface]
第2个不错~
第二个简单
第二个悲哀地没想到,第一个就更别说了
第三个问题：为什么介绍给mm好？
第一个是什么思路呢？
赞，很好
第二题... 我曾经自己想到过这题.. 但没想到解法..
看到了解析，（-_-#隐藏的真好），第二题方法很经典。
第一题要是先遍历一遍链表，将每个元素存储在另一个数组中，再random不行？好像只规定了链表只能遍历一次，而没有规定另一个数组不行，虽然有点投机取巧，但绝对符合要求(一次and随机)。^_*
回复：现在我又加了一个条件，n很大，嘻嘻
不错...
第一题。。。。不过用random算（1到n）中的随机数。。然后再算（1到n-1）随机数。。直到算（1到n-k）随机数。。。排序。。。历遍。。。能成吧。。
第二题。。想不到。。
i属于（0，n）的时候，楼主的解法才正确，否则i=n的时候，ms会溢出
汗...第二题也太简单了
第二题只会用两重循环做。
错了，是两个一重循环。
第二题
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个点被选中了，但在集合中没有被其替换的概率。
[...] Google面试题中的两道趣题 No Comments [...]
很有趣啊