如何将数组元素乘以大O(n)

Question

我有一个数字,它有N号.我想将数组元素乘以以下规则;

arr[n]={5,7,2,3,4....}

the first row:A[0]*A[2]*A[3]*A[4]....*A[n]
the second row:A[0]*A[1]*A[3]*A[4]....*A[n]
the third row:A[0]*A[1]*A[2]*A[4]...*A[n]
...........
the n row:A[0]*A[1]*A[2]*A[3]*A[4]....*A[n-1]

我用O(n ^ 2)做到了但是我无法解决它O(n)如果没有除法行元素我怎么能这样做？

Answer 1

假设阵列中没有零,可能的方法是

product = A[0]*...*A[n]
first = product / A[1]
second = product / A[2]
....

如果不允许分割,您可以使用左右运行的产品并执行以下操作:

int P[N], Q[N];
P[0] = A[0];
for(int i = 1; i < N; ++i)
    P[i] = P[i - 1] * A[i];
Q[N-1] = A[N-1]; 
for(int i = N-2; i >= 0; --i)
    Q[i] = Q[i+1] * A[i];

for(int i = 1; ....)
    R[i] = P[i-1] * Q[i+1];