给定一个数字数组，返回所有其他数字的产品数组(无除法)

I was asked this question in a job interview, and I'd like to know how others would solve it. I'm most comfortable with Java, but solutions in other languages are welcome.

在一次求职面试中，我被问到这个问题，我想知道其他人是如何解决这个问题的。我最喜欢使用Java，但是其他语言的解决方案是受欢迎的。

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i.

给定一组数字，nums，返回一组数字产品，其中产品[i]是所有nums[j]， j != i的乘积。

Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
      = [120, 60, 40, 30, 24]

You must do this in O(N) without using division.

你必须在不使用除法的情况下使用O(N)。

34 个解决方案

#1

An explanation of polygenelubricants method is: The trick is to construct the arrays (in the case for 4 elements)

polygenelubricants方法的解释是:关键是构造数组(在4个元素的情况下)

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

Both of which can be done in O(n) by starting at the left and right edges respectively.

这两种方法都可以在O(n)中分别从左右边开始。

Then multiplying the two arrays element by element gives the required result

然后将两个数组元素相乘，得到所需的结果。

My code would look something like this:

我的代码是这样的:

int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i) {
  products_below[i]=p;
  p*=a[i];
}

int products_above[N];
p=1;
for(int i=N-1;i>=0;--i) {
  products_above[i]=p;
  p*=a[i];
}

int products[N]; // This is the result
for(int i=0;i<N;++i) {
  products[i]=products_below[i]*products_above[i];
}

If you need to be O(1) in space too you can do this (which is less clear IMHO)

如果你需要在空间里做O(1)你也可以这样做(这一点不太清楚)

int a[N] // This is the input
int products[N];

// Get the products below the current index
p=1;
for(int i=0;i<N;++i) {
  products[i]=p;
  p*=a[i];
}

// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i) {
  products[i]*=p;
  p*=a[i];
}

#2

Here is a small recursive function (in C++) to do the modofication in place. It requires O(n) extra space (on stack) though. Assuming the array is in a and N holds the array length, we have

这里是一个小的递归函数(在c++中)，以执行modofication。它需要O(n)额外的空间(在堆栈上)。假设数组在a和N中保持数组长度，我们有。

int multiply(int *a, int fwdProduct, int indx) {
    int revProduct = 1;
    if (indx < N) {
       revProduct = multiply(a, fwdProduct*a[indx], indx+1);
       int cur = a[indx];
       a[indx] = fwdProduct * revProduct;
       revProduct *= cur;
    }
    return revProduct;
}

#3

Here's my attempt to solve it in Java. Apologies for the non-standard formatting, but the code has a lot of duplication, and this is the best I can do to make it readable.

这是我用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]"
    }
}

The loop invariants are pi = nums[0] * nums[1] *.. nums[i-1] and pj = nums[N-1] * nums[N-2] *.. nums[j+1]. The i part on the left is the "prefix" logic, and the j part on the right is the "suffix" logic.

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

---

Recursive one-liner

Jasmeet gave a (beautiful!) recursive solution; I've turned it into this (hideous!) Java one-liner. It does in-place modification, with O(N) temporary space in the stack.

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]"

#4

Translating Michael Anderson's solution into Haskell:

将Michael Anderson的解决方案翻译成Haskell:

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

#5

Sneakily circumventing the "no divisions" rule:

偷偷地绕过“没有分歧”的规则:

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

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

#6

Here you go, simple and clean solution with O(N) complexity:

在这里，你可以用O(N)复杂度来简单、简洁的解决方案:

int[] a = {1,2,3,4,5};
    int[] r = new int[a.length];
    int x = 1;
    r[0] = 1;
    for (int i=1;i<a.length;i++){
        r[i]=r[i-1]*a[i-1];
    }
    for (int i=a.length-1;i>0;i--){
        x=x*a[i];
        r[i-1]=x*r[i-1];
    }
    for (int i=0;i<r.length;i++){
        System.out.println(r[i]);
    }

#7

C++, 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));

#8

1. Travel Left->Right and keep saving product. Call it Past. -> O(n)
2. 左->右转，保存产品。叫它过去。- > O(n)
3. Travel Right -> left keep the product. Call it Future. -> O(n)
4. 右移->保留产品。叫它的未来。- > O(n)
5. Result[i] = Past[i-1] * future[i+1] -> O(n)
6. 结果[i] = Past[i-1] * future[i+1] -> O(n)
7. Past[-1] = 1; and Future[n+1]=1;
8. 过去[1]= 1;和未来(n + 1)= 1;

O(n)

O(n)

#9

Here is my solution in modern C++. It makes use of std::transform and is pretty easy to remember.

这是我在现代c++中的解决方案。它利用了std::transform并且很容易记住。

Online code (wandbox).

在线代码(wandbox)。

#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

vector<int>& multiply_up(vector<int>& v){
    v.insert(v.begin(),1);
    transform(v.begin()+1, v.end()
             ,v.begin()
             ,v.begin()+1
             ,[](auto const& a, auto const& b) { return b*a; }
             );
    v.pop_back();
    return v;
}

int main() {
    vector<int> v = {1,2,3,4,5};
    auto vr = v;

    reverse(vr.begin(),vr.end());
    multiply_up(v);
    multiply_up(vr);
    reverse(vr.begin(),vr.end());

    transform(v.begin(),v.end()
             ,vr.begin()
             ,v.begin()
             ,[](auto const& a, auto const& b) { return b*a; }
             );

    for(auto& i: v) cout << i << " "; 
}

#10

This is O(n^2) but f# is soooo beautiful:

这是O(n ^ 2)但f#是如此如此的美丽:

List.fold (fun seed i -> List.mapi (fun j x -> if i=j+1 then x else x*i) seed) 
          [1;1;1;1;1]
          [1..5]

#11

Tricky:

技巧:

Use the following:

使用以下:

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

Yes, I am sure i missed some i-1 instead of i, but thats the way to solve it.

是的，我肯定我错过了一些I -1而不是I，但这是解决它的方法。

#12

There also is a O(N^(3/2)) non-optimal solution. It is quite interesting, though.

还有一个O(N ^(3/2))最优的解决方案。不过，这很有趣。

First preprocess each partial multiplications of size N^0.5(this is done in O(N) time complexity). Then, calculation for each number's other-values'-multiple can be done in 2*O(N^0.5) time(why? because you only need to multiple the last elements of other ((N^0.5) - 1) numbers, and multiply the result with ((N^0.5) - 1) numbers that belong to the group of the current number). Doing this for each number, one can get O(N^(3/2)) time.

首先进行预处理每个部分乘法大小N ^ 0.5(这是O(N)时间复杂度)。然后,计算每个数量的其他值的多个可以做2 * O(N ^ 0.5)时间(为什么?因为您只需要多个其他元素((N 0.5) - 1)的多个元素，并将其结果与属于当前数字组的((N 0.5) - 1)相乘。这样做对于每一个数字,一个可以得到O(N ^(3/2))。

Example:

例子:

4 6 7 2 3 1 9 5 8

4 6 7 2 3 1 9 5 8。

partial results: 4*6*7 = 168 2*3*1 = 6 9*5*8 = 360

部分结果:4*6*7 = 168 2*3*1 = 6 9*5*8 = 360。

To calculate the value of 3, one needs to multiply the other groups' values 168*360, and then with 2*1.

要计算3的值，需要将其他组的值乘以168*360，然后再乘以2*1。

#13

public static void main(String[] args) {
    int[] arr = { 1, 2, 3, 4, 5 };
    int[] result = { 1, 1, 1, 1, 1 };
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < i; j++) {
            result[i] *= arr[j];

        }
        for (int k = arr.length - 1; k > i; k--) {
            result[i] *= arr[k];
        }
    }
    for (int i : result) {
        System.out.println(i);
    }
}

This solution i came up with and i found it so clear what do you think!?

我找到了这个解决方案，我发现它很清楚，你怎么看?

#14

Precalculate the product of the numbers to the left and to the right of each element. For every element the desired value is the product of it's neigbors's products.

预先计算每个元素的左边和右边的数字的乘积。对每个元素来说，期望的价值是它的产品。

#include <stdio.h>

unsigned array[5] = { 1,2,3,4,5};

int main(void)
{
unsigned idx;

unsigned left[5]
        , right[5];
left[0] = 1;
right[4] = 1;

        /* calculate products of numbers to the left of [idx] */
for (idx=1; idx < 5; idx++) {
        left[idx] = left[idx-1] * array[idx-1];
        }

        /* calculate products of numbers to the right of [idx] */
for (idx=4; idx-- > 0; ) {
        right[idx] = right[idx+1] * array[idx+1];
        }

for (idx=0; idx <5 ; idx++) {
        printf("[%u] Product(%u*%u) = %u\n"
                , idx, left[idx] , right[idx]  , left[idx] * right[idx]  );
        }

return 0;
}

Result:

结果:

$ ./a.out
[0] Product(1*120) = 120
[1] Product(1*60) = 60
[2] Product(2*20) = 40
[3] Product(6*5) = 30
[4] Product(24*1) = 24

(UPDATE: now I look closer, this uses the same method as Michael Anderson, Daniel Migowski and polygenelubricants above)

(更新:现在我看得更近了，这和Michael Anderson, Daniel Migowski和polygenelubricants的使用方法相同)

#15

def productify(arr, prod, i):
    if i < len(arr):
            prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1)
            retval = productify(arr, prod, i + 1)
            prod[i] *= retval
            return retval * arr[i]
    return 1

arr = [1, 2, 3, 4, 5] prod = [] productify(arr, prod, 0) print prod

arr = [1,2,3,4,5] prod = [] productify(arr, prod, 0) print prod。

#16

Well,this solution can be considered that of C/C++. Lets say we have an array "a" containing n elements like a[n],then the pseudo code would be as below.

这个解可以考虑为C/ c++。假设我们有一个包含n个元素的数组，比如[n]，那么伪代码如下。

for(j=0;j<n;j++)
  { 
    prod[j]=1;

    for (i=0;i<n;i++)
    {   
        if(i==j)
        continue;  
        else
        prod[j]=prod[j]*a[i];
  }

#17

One more solution, Using division. with twice traversal. Multiply all the elements and then start dividing it by each element.

再来一个解，用除法。两次遍历。将所有元素相乘，然后将其除以每个元素。

#18

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

#19

Here is my code:

这是我的代码:

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

#20

Here's a slightly functional example, using C#:

这里有一个稍微实用的例子，使用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]();
                }
            }

I'm not entirely certain that this is O(n), due to the semi-recursion of the created Funcs, but my tests seem to indicate that it's O(n) in time.

我不完全确定这是O(n)，由于创建的函数的半递归，但我的测试似乎表明它是O(n)的时间。

#21

To be complete here is the code in Scala:

这里要完成的是Scala的代码:

val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))

This will print out the following:

这将打印出以下内容:

120
60
40
30
24

The program will filter out the current elem (_ != elem); and multiply the new list with reduceLeft method. I think this will be O(n) if you use scala view or Iterator for lazy eval.

该程序将过滤掉当前的elem (_ != elem);并将新列表与还原法相乘。我认为如果您使用scala视图或迭代器来进行lazy eval，这将是O(n)。

#22

// This is the recursive solution in Java // Called as following from main product(a,1,0);

//这是Java //调用的递归解决方案，主要产品(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;
}

#23

A neat solution with O(n) runtime:

一个与O(n)运行时的简洁解决方案:

1. For each element calculate the product of all the elements that occur before that and it store in an array "pre".
2. 对于每个元素，计算之前发生的所有元素的乘积，并在数组“pre”中存储。
3. For each element calculate the product of all the elements that occur after that element and store it in an array "post"
4. 对于每个元素，计算在该元素之后发生的所有元素的乘积，并将其存储在数组“post”中

5. Create a final array "result", for an element i,

   创建一个最终的数组“result”，作为元素i，

   result[i] = pre[i-1]*post[i+1];
   

#24

function solution($array)
{
    $result = [];
    foreach($array as $key => $value){
        $copyOfOriginalArray = $array;
        unset($copyOfOriginalArray[$key]);
        $result[$key] = multiplyAllElemets($copyOfOriginalArray);
    }
    return $result;
}

/**
 * multiplies all elements of array
 * @param $array
 * @return int
 */
function multiplyAllElemets($array){
    $result = 1;
    foreach($array as $element){
        $result *= $element;
    }
    return $result;
}

$array = [1, 9, 2, 7];

print_r(solution($array));

#25

Here is another simple concept which solves the problem in O(N).

这里是另一个简单的概念，它解决了O(N)中的问题。

        int[] arr = new int[] {1, 2, 3, 4, 5};
        int[] outArray = new int[arr.length]; 
        for(int i=0;i<arr.length;i++){
            int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b);
            outArray[i] = res/arr[i];
        }
        System.out.println(Arrays.toString(outArray));

#26

We can exclude the nums[j] (where j != i) from list first, then get the product of the rest; The following is a python way to solve this puzzle:

我们可以将nums[j] (j != i)从列表中排除，然后得到其余的乘积;下面是一个python方法来解决这个难题:

def products(nums):
    return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print products([1, 2, 3, 4, 5])

[out]
[120, 60, 40, 30, 24]

#27

Based on Billz answer--sorry I can't comment, but here is a scala version that correctly handles duplicate items in the list, and is probably O(n):

基于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

returns:

返回:

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

#28

I have a solution with O(n) space and O(n^2) time complexity provided below,

我有一个解决方案与O(n)O(n ^ 2)时间复杂度和空间提供了以下,

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

#29

Here is the ptyhon version

这是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

#30

I got asked this question recently, and whilst I couldn't get O(N) during it, I had a different approach (unfortunately O(N^2)) but thought I'd share anyway.

最近我问这个问题,虽然我无法在O(N),我有一个不同的方法(不幸的是O(N ^ 2)),但想我分享。

Convert to List<Integer> first.

先转换为列表 <整数> 。

Loop through original array array.length() times.

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

Use a while loop to multiple the next set of required numbers:

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

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

Then add res to a new array (which of course you've declared earlier), then add the value at array[i] to the List, and continue so forth.

然后将res添加到一个新数组中(当然您之前已经声明过了)，然后将数组[i]的值添加到列表中，并继续这样做。

I know this won't be of great use, but it's what I came up with under the pressures of an interview :)

我知道这不会很有用，但这是我在面试的压力下想到的。

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

Output: [24, 120, 60, 40, 30]

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