上下两次。在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;
    }

最近有人问我这个问题，虽然我不能得到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]

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

根据Billz的回答——抱歉我不能评论，但这里是一个正确处理列表中重复项的scala版本，可能是O(n):

val list1 = List(1, 7, 3, 3, 4, 4)
val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)}
view.force

返回:

List(1008, 144, 336, 336, 252, 252)

下面是我使用python的简洁解决方案。

from functools import reduce

def excludeProductList(nums_):
    after = [reduce(lambda x, y: x*y, nums_[i:]) for i in range(1, len(nums_))] + [1]
    before = [1] + [reduce(lambda x, y: x*y, nums_[:i]) for i in range(1, len(nums_))]
    zippedList =  list(zip(before, after))
    finalList = list(map(lambda x: x[0]*x[1], zippedList))
    return finalList

技巧:

使用以下方法:

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