我有一个O(n)空间和O(n²)时间复杂度的解，如下所示，

public static int[] findEachElementAsProduct1(final int[] arr) {

        int len = arr.length;

//        int[] product = new int[len];
//        Arrays.fill(product, 1);

        int[] product = IntStream.generate(() -> 1).limit(len).toArray();


        for (int i = 0; i < len; i++) {

            for (int j = 0; j < len; j++) {

                if (i == j) {
                    continue;
                }

                product[i] *= arr[j];
            }
        }

        return product;
    }

我习惯使用c#:

    public int[] ProductExceptSelf(int[] nums)
    {
        int[] returnArray = new int[nums.Length];
        List<int> auxList = new List<int>();
        int multTotal = 0;

        // If no zeros are contained in the array you only have to calculate it once
        if(!nums.Contains(0))
        {
            multTotal = nums.ToList().Aggregate((a, b) => a * b);

            for (int i = 0; i < nums.Length; i++)
            {
                returnArray[i] = multTotal / nums[i];
            }
        }
        else
        {
            for (int i = 0; i < nums.Length; i++)
            {
                auxList = nums.ToList();
                auxList.RemoveAt(i);
                if (!auxList.Contains(0))
                {
                    returnArray[i] = auxList.Aggregate((a, b) => a * b);
                }
                else
                {
                    returnArray[i] = 0;
                }
            }
        }            

        return returnArray;
    }

这里有一个小的递归函数(在c++中)来进行修改。它需要O(n)额外的空间(在堆栈上)。假设数组在a中，N表示数组长度，我们有:

int multiply(int *a, int fwdProduct, int indx) {
    int revProduct = 1;
    if (indx < N) {
       revProduct = multiply(a, fwdProduct*a[indx], indx+1);
       int cur = a[indx];
       a[indx] = fwdProduct * revProduct;
       revProduct *= cur;
    }
    return revProduct;
}

下面是一个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.

预先计算每个元素左右两边数字的乘积。 对于每个元素，期望值都是它相邻元素乘积的乘积。

#include <stdio.h>

unsigned array[5] = { 1,2,3,4,5};

int main(void)
{
unsigned idx;

unsigned left[5]
        , right[5];
left[0] = 1;
right[4] = 1;

        /* calculate products of numbers to the left of [idx] */
for (idx=1; idx < 5; idx++) {
        left[idx] = left[idx-1] * array[idx-1];
        }

        /* calculate products of numbers to the right of [idx] */
for (idx=4; idx-- > 0; ) {
        right[idx] = right[idx+1] * array[idx+1];
        }

for (idx=0; idx <5 ; idx++) {
        printf("[%u] Product(%u*%u) = %u\n"
                , idx, left[idx] , right[idx]  , left[idx] * right[idx]  );
        }

return 0;
}

结果:

$ ./a.out
[0] Product(1*120) = 120
[1] Product(1*60) = 60
[2] Product(2*20) = 40
[3] Product(6*5) = 30
[4] Product(24*1) = 24

(更新:现在我仔细看，这使用与Michael Anderson, Daniel Migowski和上面的聚基因润滑剂相同的方法)

还有一个O(N^(3/2))非最优解。不过，这很有趣。

首先预处理大小为N^0.5的每个部分乘法(这在O(N)时间复杂度中完成)。然后，计算每个数字的其他值的倍数可以在2*O(N^0.5)时间内完成(为什么?因为您只需要将其他((N^0.5) - 1)数字的最后一个元素相乘，并将结果与属于当前数字组的((N^0.5) - 1)数字相乘。对每一个数都这样做，可以得到O(N^(3/2))时间。

例子:

4, 6, 7, 2, 3, 1, 9, 5, 8

部分结果: 4*6*7 = 168 2*3*1 = 6 9*5*8 = 360

要计算3的值，需要将其他组的值乘以168*360，然后乘以2*1。