4.19 如何按要求构造新的数组
【出自BD笔试题】
难度系数：★★★☆☆ 被考察系数：★★★★☆
题目描述：
给定一个数组a[N]，希望构造一个新的数组b[N]，其中，b[i]=a[0]*a[1]*…*a[N-1]/a[i]。在构造数组的过程中，有如下几点要求：
（1）不允许使用除法。
（2）要求O（1）空间复杂度和O（N）时间复杂度。
（3）除遍历计数器与a[N]、b[N]外，不可以使用新的变量（包括栈临时变量、堆空间和全局静态变量等）。
（4）请用程序实现并简单描述。
分析与解答：
如果没有时间复杂度与空间复杂度的要求，算法将非常简单。首先遍历一遍数组a，计算数组a中所有元素的乘积，并保存到一个临时变量tmp中，然后再遍历一遍数组a并给数组赋值：b[i]=tmp/a[i]，但是这种方法使用了一个临时变量，因此，不满足题目的要求。下面介绍另外一种方法。
在计算b[i]的时候，只要将数组a中除了a[i]以外的所有值相乘即可。这种方法的主要思路是：首先遍历一遍数组a，在遍历的过程中对数组b进行赋值：b[i]=a[i-1]*b[i-1]，这样经过一次遍历后，数组b的值为b[i]=a[0]*a[1]*…*a[i-1]。此时只需要将数组中的值b[i]再乘以a[i+1]*a[i+2]*…a[N-1]，实现方法为逆向遍历数组a，把数组后半段值的乘积记录到b[0]中，通过b[i]与b[0]的乘积就可以得到满足题目要求的b[i]，具体而言，执行b[i]=b[i]*b[0]（首先执行的目的是为了保证在执行下面一个计算的时候，b[0]中不包含与b[i]的乘积），接着记录数组后半段的乘积到b[0]中：b[0]*=b[0]*a[i]。
实现代码如下：
程序的运行结果如下：3628800 1814400 1209600 907200 725760 604800 518400 453600 403200 362880