本文共 959 字，大约阅读时间需要 3 分钟。
已知一个包含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]; }} 转载地址：http://tnnvi.baihongyu.com/