我在一次工作面试中被问到这个问题,我想知道其他人是如何解决这个问题的。我最擅长使用Java,但也欢迎使用其他语言的解决方案。

给定一个数字数组nums,返回一个数字数组products,其中products[i]是所有nums[j]的乘积,j != i。 输入:[1,2,3,4,5] 输出:[(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] 你必须在O(N)中不使用除法来做这个。


当前回答

这个解决方案可以被认为是C/ c++的。 假设我们有一个包含n个元素的数组a 像a[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];
  }

其他回答

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

if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5]
    prod = []
    productify(arr, prod, 0)
    print(prod)

试试这个!

import java.util.*;
class arrProduct
{
 public static void main(String args[])
     {
         //getting the size of the array
         Scanner s = new Scanner(System.in);
            int noe = s.nextInt();

        int out[]=new int[noe];
         int arr[] = new int[noe];

         // getting the input array
         for(int k=0;k<noe;k++)
         {
             arr[k]=s.nextInt();
         }

         int val1 = 1,val2=1;
         for(int i=0;i<noe;i++)
         {
             int res=1;

                 for(int j=1;j<noe;j++)
                 {
                if((i+j)>(noe-1))
                {

                    int diff = (i+j)-(noe);

                    if(arr[diff]!=0)
                    {
                    res = res * arr[diff];
                    }
                }

                else
                {
                    if(arr[i+j]!=0)
                    {
                    res= res*arr[i+j];
                    }
                }


             out[i]=res;

         }
         }

         //printing result
         System.out.print("Array of Product: [");
         for(int l=0;l<out.length;l++)
         {
             if(l!=out.length-1)
             {
            System.out.print(out[l]+",");
             }
             else
             {
                 System.out.print(out[l]);
             }
         }
         System.out.print("]");
     }

}

这个解决方案可以被认为是C/ c++的。 假设我们有一个包含n个元素的数组a 像a[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];
  }

我用Javascript想出了两个解决方案,一个有除法,一个没有

//不除法 函数methodOne(arr) { 加勒比海盗。Map (item => { 加勒比海盗。Reduce ((result, num) => { If (num !== item) { 结果=结果* num; } 返回结果; }, 1) }); } //使用除法 函数methodTwo(arr) { Var mul = arr。Reduce ((result, num) => { 结果=结果* num; 返回结果; }, 1) 加勒比海盗。Map (item => mul/item); } console.log(methodOne([1,2,3,4,5])); console.log(methodTwo([1,2,3,4,5]));

ruby的解决方案

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