在这里添加我的javascript解决方案，因为我没有发现任何人建议这样做。 除法是什么，除了数从另一个数中得到一个数的次数吗?我计算了整个数组的乘积，然后遍历每个元素，并减去当前元素直到0:

//No division operation allowed
// keep substracting divisor from dividend, until dividend is zero or less than divisor
function calculateProducsExceptCurrent_NoDivision(input){
  var res = [];
  var totalProduct = 1;
  //calculate the total product
  for(var i = 0; i < input.length; i++){
    totalProduct = totalProduct * input[i];
  }
  //populate the result array by "dividing" each value
  for(var i = 0; i < input.length; i++){
    var timesSubstracted = 0;
    var divisor = input[i];
    var dividend = totalProduct;
    while(divisor <= dividend){
      dividend = dividend - divisor;
      timesSubstracted++;
    }
    res.push(timesSubstracted);
  }
  return res;
}

//这是Java中的递归解决方案 //从main product(a,1,0)调用如下;

public static double product(double[] a, double fwdprod, int index){
    double revprod = 1;
    if (index < a.length){
        revprod = product2(a, fwdprod*a[index], index+1);
        double cur = a[index];
        a[index] = fwdprod * revprod;
        revprod *= cur;
    }
    return revprod;
}

还有一个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。

这是我的代码:

int multiply(int a[],int n,int nextproduct,int i)
{
    int prevproduct=1;
    if(i>=n)
        return prevproduct;
    prevproduct=multiply(a,n,nextproduct*a[i],i+1);
    printf(" i=%d > %d\n",i,prevproduct*nextproduct);
    return prevproduct*a[i];
}

int main()
{
    int a[]={2,4,1,3,5};
    multiply(a,5,1,0);
    return 0;
}

{-
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)

技巧:

使用以下方法:

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