面试题：忘我之乘积；及蓄水池抽样精妙解法

arron刘

今日面试题：忘我之乘积



给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B=A[1]*A[2]*...*A[n]/A。你不能使用除法运算。



=====================================

蓄水池抽样（Reservoir Sampling)问题分析http://bbs.chinaunix.net/thread-4092861-1-1.html



问题：
要求从N个元素中随机的抽取k个元素，其中N无法确定。

这种应用的场景一般是数据流的情况下，由于数据只能被读取一次，而且数据量很大，并不能全部保存，因此数据量N是无法在抽样开始时确定的；但又要保持随机性，于是有了这个问题。所以搜索网站有时候会问这样的问题。

这里的核心问题就是“随机”，怎么才能是随机的抽取元素呢？我们设想，买彩票的时候，由于所有彩票的中奖概率都是一样的，所以我们才是“随机的”买彩票。那么要使抽取数据也随机，必须使每一个数据被抽样出来的概率都一样。

分析：

由于N无法确定，数据只能读取一次，并且要求随机，就是每个元素抽出的概率一样，都是k/N。

面试的时候，经常会在纸上通过一个小的例子来找到好的解决方案。比如先让你从100个元素中等概率抽取出10个元素。后来又向集合中添加了20个元素，变成了120个元素等概率抽取10个，怎么样才能随着N的动态改变而让N无论等于多少时这N个元素都等概率被抽取呢？

解法一：最小k个指纹
找到一个哈希函数能产生随机数，同时用一个k个元素的堆用来保存最小的k个元素。那么过一遍所有的元素，计算每个的哈希值，通过堆来选择k个元素。
这个算法看起来很精妙，会有什么问题吗？（思考）

解法二：数学计算
先选中前k个， 从第k+1个元素到最后一个元素为止， 以1/i  (i=k+1, k+2,...,N) 的概率选中第i个元素， 并且随机替换掉一个原先选中的元素， 这样遍历一次得到k个元素， 可以保证完全随机选取。
看来简单的算法，怎么能确保每个元素被选中的概率是k/N？
任意元素G在i轮留下来的概率：
P(G留下) = P(G已经存在) * P(G没有被替换)
        = P(G已经存在) * (1 - P(G被替换))
        = P(G已经存在) * (1 - P(第i个元素要替换某个元素) * P(某个元素是G))
        = (k/i) * (1 - (k/(i+1)) * (1/k))
        = (k/i) * (1 - (1/(i+1)))
        = (k/i) * (i/(i+1))
        = (k/(i+1))
证毕！


这个题有很多的变种，比如，
给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）
从一个不知长度的文件中随机抽出k行。
从实时的搜索词中随机抽出k个词。

arron刘

分析：

看到题目，不要紧张，要头脑清晰，看穿面试官的本意，实际上，他是用除法公式，但又要求不用除法来迷惑你。

要求在不使用除法的情况下计算B=A[0]*…*A[n]/A，简单变换一下形式，即可得到B=A[0]*…*A[i-1]*A[i+1]*…*A[n]，一共n-1次乘法。每一个B计算一遍，总的时间复杂度为O(n^2)。不符合题目要求，必须减少乘法的次数。如何减少乘法的次数呢？
继续分析，通过上面的变换，我们可以得到B是由两部分相乘得到的：
A[0]*…*A[i-1]
A[i+1]*…*A[n]
先看第一部分，在计算B[i+1]的时候，是可以利用B的第一部分结果的，只需要乘以A即得到B[i+1]的第一部分。
第二部分同理，计算完A[i+1]*…*A[n]，再计算A*A[i+1]*…*A[n]，只需要乘以A即可。A*A[i+1]*…*A[n]是B[i-1]的第二部分。
由此分析，构建两个新的数组：C和D（为了方便解释，用了两个数组），
C = A[0]*…*A[i-1] = C[i-1]*A[i-1]
D = A[i+1]*…*A[n] = D[i+1]*A[i+1}
构建C和D都是O(n)的时间复杂度（C从前到后遍历一遍数组，D从后到前遍历一边数组），然后，B = C*D也是O(n)的时间复杂度。整体算法的时间复杂度是O(n)。

题目到这解答完毕。

但是面试官的问题还没有完，他们会继续问，这个解法的空间是O(n)的，能够空间O(1)的情况下实现么？

首先看看一个只有5个数的数组，A[1]，A[2]，A[3]，A[4]，A[5]。

首先从头到尾遍历：

B[1] = A[1]
B[2] = B[1]*A[2]
B[3] = B[2]*A[3]
B[4] = B[3]*A[4]
B[5] = B[4], 临时变量 C=A[5]

然后从尾到头遍历：

B[4] = B[3]*C, C=C*A[4]
B[3] = B[2]*C, C=C*A[3]
B[2] = B[1]*C, C=C*A[2]
B[1] = C

通过这个小的例子，我们得到了算法，然后可以推广到任意多的元素。这个是面试中常用的技巧。

大家可以自己尝试把算法变成代码。