最近有人问我这个问题，虽然我不能得到O(N)，但我有一个不同的方法(不幸的是O(N²))，但我想无论如何都要分享。

首先转换为列表<Integer>。

遍历原始数组array.length()次。

使用while循环乘下一组所需的数字:

while (temp < list.size() - 1) {
    res *= list.get(temp);
    temp++;
}

然后将res添加到一个新数组(当然，您已经在前面声明了)，然后将数组[i]的值添加到List，依此类推。

我知道这不会有太大的用处，但这是我在面试的压力下想到的:)

    int[] array = new int[]{1, 2, 3, 4, 5};
    List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
    int[] newarray = new int[array.length];
    int res = 1;
    for (int i = 0; i < array.length; i++) {
        int temp = i;
        while (temp < list.size() - 1) {
            res *= list.get(temp);
            temp++;
        }
        newarray[i] = res;
        list.add(array[i]);
        res = 1;
    }

输出:[24,120,60,40,30]

在这里添加我的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;
}

ruby的解决方案

a = [1,2,3,4]
result = []
a.each {|x| result.push( (a-[x]).reject(&:zero?).reduce(:*)) }
puts 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]))

    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];
            }
        }
    }

我的第一次尝试，用Python。O (2 n):

def product(l):
    product = 1
    num_zeroes = 0
    pos_zero = -1

    # Multiply all and set positions
    for i, x in enumerate(l):
        if x != 0:
            product *= x
            l[i] = 1.0/x
        else:
            num_zeroes += 1
            pos_zero = i

    # Warning! Zeroes ahead!
    if num_zeroes > 0:
        l = [0] * len(l)

        if num_zeroes == 1:
            l[pos_zero] = product

    else:
        # Now set the definitive elements
        for i in range(len(l)):
            l[i] = int(l[i] * product)

    return l


if __name__ == "__main__":
    print("[0, 0, 4] = " + str(product([0, 0, 4])))
    print("[3, 0, 4] = " + str(product([3, 0, 4])))
    print("[1, 2, 3] = " + str(product([1, 2, 3])))
    print("[2, 3, 4, 5, 6] = " + str(product([2, 3, 4, 5, 6])))
    print("[2, 1, 2, 2, 3] = " + str(product([2, 1, 2, 2, 3])))

输出:

[0, 0, 4] = [0, 0, 0]
[3, 0, 4] = [0, 12, 0]
[1, 2, 3] = [6, 3, 2]
[2, 3, 4, 5, 6] = [360, 240, 180, 144, 120]
[2, 1, 2, 2, 3] = [12, 24, 12, 12, 8]