我有一个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;
    }

试试这个!

import java.util.*;
class arrProduct
{
 public static void main(String args[])
     {
         //getting the size of the array
         Scanner s = new Scanner(System.in);
            int noe = s.nextInt();

        int out[]=new int[noe];
         int arr[] = new int[noe];

         // getting the input array
         for(int k=0;k<noe;k++)
         {
             arr[k]=s.nextInt();
         }

         int val1 = 1,val2=1;
         for(int i=0;i<noe;i++)
         {
             int res=1;

                 for(int j=1;j<noe;j++)
                 {
                if((i+j)>(noe-1))
                {

                    int diff = (i+j)-(noe);

                    if(arr[diff]!=0)
                    {
                    res = res * arr[diff];
                    }
                }

                else
                {
                    if(arr[i+j]!=0)
                    {
                    res= res*arr[i+j];
                    }
                }


             out[i]=res;

         }
         }

         //printing result
         System.out.print("Array of Product: [");
         for(int l=0;l<out.length;l++)
         {
             if(l!=out.length-1)
             {
            System.out.print(out[l]+",");
             }
             else
             {
                 System.out.print(out[l]);
             }
         }
         System.out.print("]");
     }

}

下面是我尝试用Java来解决这个问题。抱歉格式不规范，但代码有很多重复，这是我能做的最好的，使它可读。

import java.util.Arrays;

public class Products {
    static int[] products(int... nums) {
        final int N = nums.length;
        int[] prods = new int[N];
        Arrays.fill(prods, 1);
        for (int
           i = 0, pi = 1    ,  j = N-1, pj = 1  ;
           (i < N)         && (j >= 0)          ;
           pi *= nums[i++]  ,  pj *= nums[j--]  )
        {
           prods[i] *= pi   ;  prods[j] *= pj   ;
        }
        return prods;
    }
    public static void main(String[] args) {
        System.out.println(
            Arrays.toString(products(1, 2, 3, 4, 5))
        ); // prints "[120, 60, 40, 30, 24]"
    }
}

循环不变量为pi = nums[0] * nums[1] *..* nums[N-2] *..num [j + 1]。左边的i部分是“前缀”逻辑，右边的j部分是“后缀”逻辑。

递归一行程序

Jasmeet给出了一个(漂亮的!)递归解;我把它变成了这样(可怕!)Java一行程序。它进行就地修改，堆栈中有O(N)个临时空间。

static int multiply(int[] nums, int p, int n) {
    return (n == nums.length) ? 1
      : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1))
          + 0*(nums[n] *= p);
}

int[] arr = {1,2,3,4,5};
multiply(arr, 1, 0);
System.out.println(Arrays.toString(arr));
// prints "[120, 60, 40, 30, 24]"

下面是一个使用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)。

c++, O (n):

long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies<int>());
transform(in.begin(), in.end(), back_inserter(res),
          bind1st(divides<long long>(), prod));

{-
Recursive solution using sqrt(n) subsets. Runs in O(n).

Recursively computes the solution on sqrt(n) subsets of size sqrt(n). 
Then recurses on the product sum of each subset.
Then for each element in each subset, it computes the product with
the product sum of all other products.
Then flattens all subsets.

Recurrence on the run time is T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + n

Suppose that T(n) ≤ cn in O(n).

T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + n
    ≤ sqrt(n)*c*sqrt(n) + c*sqrt(n) + n
    ≤ c*n + c*sqrt(n) + n
    ≤ (2c+1)*n
    ∈ O(n)

Note that ceiling(sqrt(n)) can be computed using a binary search 
and O(logn) iterations, if the sqrt instruction is not permitted.
-}

otherProducts [] = []
otherProducts [x] = [1]
otherProducts [x,y] = [y,x]
otherProducts a = foldl' (++) [] $ zipWith (\s p -> map (*p) s) solvedSubsets subsetOtherProducts
    where 
      n = length a

      -- Subset size. Require that 1 < s < n.
      s = ceiling $ sqrt $ fromIntegral n

      solvedSubsets = map otherProducts subsets
      subsetOtherProducts = otherProducts $ map product subsets

      subsets = reverse $ loop a []
          where loop [] acc = acc
                loop a acc = loop (drop s a) ((take s a):acc)