上下两次。在O(N)完成的工作

private static int[] multiply(int[] numbers) {
        int[] multiplied = new int[numbers.length];
        int total = 1;

        multiplied[0] = 1;
        for (int i = 1; i < numbers.length; i++) {
            multiplied[i] = numbers[i - 1] * multiplied[i - 1];
        }

        for (int j = numbers.length - 2; j >= 0; j--) {
            total *= numbers[j + 1];
            multiplied[j] = total * multiplied[j];
        }

        return multiplied;
    }

这是ptyhon版本

  # This solution use O(n) time and O(n) space
  def productExceptSelf(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    N = len(nums)
    if N == 0: return

    # Initialzie list of 1, size N
    l_prods, r_prods = [1]*N, [1]*N

    for i in range(1, N):
      l_prods[i] = l_prods[i-1] * nums[i-1]

    for i in reversed(range(N-1)):
      r_prods[i] = r_prods[i+1] * nums[i+1]

    result = [x*y for x,y in zip(l_prods,r_prods)]
    return result

  # This solution use O(n) time and O(1) space
  def productExceptSelfSpaceOptimized(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    N = len(nums)
    if N == 0: return

    # Initialzie list of 1, size N
    result = [1]*N

    for i in range(1, N):
      result[i] = result[i-1] * nums[i-1]

    r_prod = 1
    for i in reversed(range(N)):
      result[i] *= r_prod
      r_prod *= nums[i]

    return result

鬼鬼祟祟地绕过“不划分”规则:

sum = 0.0
for i in range(a):
  sum += log(a[i])

for i in range(a):
  output[i] = exp(sum - log(a[i]))

技巧:

使用以下方法:

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，但这是解决它的方法。

以下是线性O(n)时间内的简单Scala版本:

def getProductEff(in:Seq[Int]):Seq[Int] = {

   //create a list which has product of every element to the left of this element
   val fromLeft = in.foldLeft((1, Seq.empty[Int]))((ac, i) => (i * ac._1, ac._2 :+ ac._1))._2

   //create a list which has product of every element to the right of this element, which is the same as the previous step but in reverse
   val fromRight = in.reverse.foldLeft((1,Seq.empty[Int]))((ac,i) => (i * ac._1,ac._2 :+ ac._1))._2.reverse

   //merge the two list by product at index
   in.indices.map(i => fromLeft(i) * fromRight(i))

}

这是可行的，因为本质上答案是一个数组，它是左右所有元素的乘积。

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)