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

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，返回一个数字乘积的数组，其中product [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] *。和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] =过去[i-1] *未来[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)时间(为什么?因为你只需要多个最后元素的其他((0.5 N ^)- 1),并把结果与((0.5 N ^)- 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个元素的数组“a”，那么伪代码将如下所示。

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视图或Iterator进行惰性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,

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

   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]