腾讯的一道面试题—不用除法求数字乘积

题目：

已知一个包含N个元素的数组A[N]，试求出这样一个数组OUTPUT[N]，其中OUTPUT[I]的值为数组A中除了A[i]的其他所有元素的乘积。注意，不能使用除法。时间复杂度必须为O（N）。

例如OUTPUT[0]的值为A[1]*A[2]...A[N], OUTPUT[1]的值为A[0]*A[2]...A[N]。

假定数组A={4, 3, 2, 1, 2}，则OUTPUT={12, 16, 24, 48, 24}。

分析：

初看此题，觉得很无聊，这个题目貌似没有什么意义。要是可以用除法，直接OUTPUT[I]=A[0]*A[1]...A[N]/A[i]。

但是不能用除法，而且时间复杂度为O(N)，确实一时还难以想到好的解法。如果使用暴力方法，每次求OUTPUT[I]都暴力计算一遍，那么时间复杂度为O(N^2)，达不到O(N)的要求。

我们可以定义一个数组B，其中元素B[i]的值为A[0]到A[i]的乘积，即B[i]=A[0]*A[1]...A[i]。假如A = {4, 3, 2, 1, 2}，则B = {4, 12, 24, 24, 48}。然后从右向左扫描数组A，并使用一个变量product记录从右向左扫描到当前位置的乘积。从而OUTPUT[i]=B[i-1]*product.

上面的方法采用O(N)的时间和O(N)的空间，那么是否还有更好的办法呢？是否能省去这O(N)的空间呢？

确实是的，这O(N)的空间确实可以省去。我们使用2个变量就可以满足要求。使用变量left保存从左向右扫描数组A的乘积，使用变量right保存从右向左扫描数组A的乘积。

代码：

void array_multiplication(int A[], int OUTPUT[], int n) 
{
  int left = 1;
  int right = 1;
  for (int i = 0; i < n; i++)
    OUTPUT[i] = 1;
  for (int i = 0; i < n; i++) {
    OUTPUT[i] *= left;
    OUTPUT[n - 1 - i] *= right;
    left *= A[i];
    right *= A[n - 1 - i];
  }
}