我在一次工作面试中被问到这个问题,我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。


当前回答

我用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]));

其他回答

还有一个O(N^(3/2))非最优解。不过,这很有趣。

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

例子:

4, 6, 7, 2, 3, 1, 9, 5, 8

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

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

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

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

试试这个!

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("]");
     }

}

我们正在分解数组的元素,首先从下标之前开始,即前缀,然后是下标或后缀之后

class Solution:

   def productExceptSelf(nums):

      length = len(nums)


      result = [1] * length


      prefix_product = 1


      postfix_product = 1

# we initialize the result and products


      for i in range(length)

      result[i] *= prefix_product


       prefix_product *= nums[i]

#we multiply the result by each number before the index

      for i in range(length-1,-1,-1)

      result[i] *= postfix_product


      postfix_product *= nums[i]

#same for after index
   return result

抱歉,走路时用手机