技巧:

使用以下方法:

public int[] calc(int[] params) {

int[] left = new int[n-1]
in[] right = new int[n-1]

int fac1 = 1;
int fac2 = 1;
for( int i=0; i<n; i++ ) {
    fac1 = fac1 * params[i];
    fac2 = fac2 * params[n-i];
    left[i] = fac1;
    right[i] = fac2; 
}
fac = 1;

int[] results = new int[n];
for( int i=0; i<n; i++ ) {
    results[i] = left[i] * right[i];
}

是的，我确定我错过了一些I -1而不是I，但这是解决它的方法。

我们可以先从列表中排除nums[j](其中j != i)，然后得到其余部分的乘积;下面是python解决这个难题的方法:

from functools import reduce
def products(nums):
    return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print(products([1, 2, 3, 4, 5]))

[out]
[120, 60, 40, 30, 24]

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

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

import java.util.Arrays;

public class Pratik
{
    public static void main(String[] args)
    {
        int[] array = {2, 3, 4, 5, 6};      //  OUTPUT: 360  240  180  144  120
        int[] products = new int[array.length];
        arrayProduct(array, products);
        System.out.println(Arrays.toString(products));
    }

    public static void arrayProduct(int array[], int products[])
    {
        double sum = 0, EPSILON = 1e-9;

        for(int i = 0; i < array.length; i++)
            sum += Math.log(array[i]);

        for(int i = 0; i < array.length; i++)
            products[i] = (int) (EPSILON + Math.exp(sum - Math.log(array[i])));
    }
}

输出:

[360, 240, 180, 144, 120]

时间复杂度:O(n) 空间复杂度:O(1)

    int[] arr1 = { 1, 2, 3, 4, 5 };
    int[] product = new int[arr1.Length];              

    for (int i = 0; i < arr1.Length; i++)
    {
        for (int j = 0; j < product.Length; j++)
        {
            if (i != j)
            {
                product[j] = product[j] == 0 ? arr1[i] : product[j] * arr1[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.