给你，简单干净的解决方案，复杂度为O(N):

int[] a = {1,2,3,4,5};
    int[] r = new int[a.length];
    int x = 1;
    r[0] = 1;
    for (int i=1;i<a.length;i++){
        r[i]=r[i-1]*a[i-1];
    }
    for (int i=a.length-1;i>0;i--){
        x=x*a[i];
        r[i-1]=x*r[i-1];
    }
    for (int i=0;i<r.length;i++){
        System.out.println(r[i]);
    }

下面是一个C实现 O(n)时间复杂度。 输入

#include<stdio.h>
int main()
{
    int x;
    printf("Enter The Size of Array : ");
    scanf("%d",&x);
    int array[x-1],i ;
    printf("Enter The Value of Array : \n");
      for( i = 0 ; i <= x-1 ; i++)
      {
          printf("Array[%d] = ",i);
          scanf("%d",&array[i]);
      }
    int left[x-1] , right[x-1];
    left[0] = 1 ;
    right[x-1] = 1 ;
      for( i = 1 ; i <= x-1 ; i++)
      {
          left[i] = left[i-1] * array[i-1];
      }
    printf("\nThis is Multiplication of array[i-1] and left[i-1]\n");
      for( i = 0 ; i <= x-1 ; i++)
      {
        printf("Array[%d] = %d , Left[%d] = %d\n",i,array[i],i,left[i]);
      }
      for( i = x-2 ; i >= 0 ; i--)
      {
          right[i] = right[i+1] * array[i+1];
      }
   printf("\nThis is Multiplication of array[i+1] and right[i+1]\n");
      for( i = 0 ; i <= x-1 ; i++)
      {
        printf("Array[%d] = %d , Right[%d] = %d\n",i,array[i],i,right[i]);
      }
    printf("\nThis is Multiplication of Right[i] * Left[i]\n");
      for( i = 0 ; i <= x-1 ; i++)
      {
          printf("Right[%d] * left[%d] = %d * %d = %d\n",i,i,right[i],left[i],right[i]*left[i]);
      }
    return 0 ;
}

输出

    Enter The Size of Array : 5
    Enter The Value of Array :
    Array[0] = 1
    Array[1] = 2
    Array[2] = 3
    Array[3] = 4
    Array[4] = 5

    This is Multiplication of array[i-1] and left[i-1]
    Array[0] = 1 , Left[0] = 1
    Array[1] = 2 , Left[1] = 1
    Array[2] = 3 , Left[2] = 2
    Array[3] = 4 , Left[3] = 6
    Array[4] = 5 , Left[4] = 24

    This is Multiplication of array[i+1] and right[i+1]
    Array[0] = 1 , Right[0] = 120
    Array[1] = 2 , Right[1] = 60
    Array[2] = 3 , Right[2] = 20
    Array[3] = 4 , Right[3] = 5
    Array[4] = 5 , Right[4] = 1

    This is Multiplication of Right[i] * Left[i]
    Right[0] * left[0] = 120 * 1 = 120
    Right[1] * left[1] = 60 * 1 = 60
    Right[2] * left[2] = 20 * 2 = 40
    Right[3] * left[3] = 5 * 6 = 30
    Right[4] * left[4] = 1 * 24 = 24

    Process returned 0 (0x0)   execution time : 6.548 s
    Press any key to continue.

将Michael Anderson的解决方案翻译成Haskell:

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

下面是一个使用c#的函数式示例:

            Func<long>[] backwards = new Func<long>[input.Length];
            Func<long>[] forwards = new Func<long>[input.Length];

            for (int i = 0; i < input.Length; ++i)
            {
                var localIndex = i;
                backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex];
                forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex];
            }

            var output = new long[input.Length];
            for (int i = 0; i < input.Length; ++i)
            {
                if (0 == i)
                {
                    output[i] = forwards[i + 1]();
                }
                else if (input.Length - 1 == i)
                {
                    output[i] = backwards[i - 1]();
                }
                else
                {
                    output[i] = forwards[i + 1]() * backwards[i - 1]();
                }
            }

我不完全确定这是O(n)，因为所创建的Funcs是半递归的，但我的测试似乎表明它在时间上是O(n)。

这里是Scala中的完整代码:

val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))

这将打印出以下内容:

120
60
40
30
24

程序将过滤掉当前的elem (_ != elem);并使用reducleft方法将新列表相乘。我认为这将是O(n)如果你使用scala视图或迭代器进行惰性计算。

多基因润滑剂方法的一个解释是:

诀窍是构造数组(在4个元素的情况下):

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

这两种方法都可以在O(n)中分别从左右边开始。

然后，将两个数组逐个元素相乘，得到所需的结果。

我的代码看起来是这样的:

int a[N] // This is the input
int products_below[N];
int p = 1;
for (int i = 0; i < N; ++i) {
    products_below[i] = p;
    p *= a[i];
}

int products_above[N];
p = 1;
for (int i = N - 1; i >= 0; --i) {
    products_above[i] = p;
    p *= a[i];
}

int products[N]; // This is the result
for (int i = 0; i < N; ++i) {
    products[i] = products_below[i] * products_above[i];
}

如果你也需要空间中的解是O(1)，你可以这样做(在我看来不太清楚):

int a[N] // This is the input
int products[N];

// Get the products below the current index
int p = 1;
for (int i = 0; i < N; ++i) {
    products[i] = p;
    p *= a[i];
}

// Get the products above the current index
p = 1;
for (int i = N - 1; i >= 0; --i) {
    products[i] *= p;
    p *= a[i];
}