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


当前回答

下面是我尝试用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]"
    }
}

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


递归一行程序

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

其他回答

这是我的代码:

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

下面是我尝试用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]"
    }
}

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


递归一行程序

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

JavaScript中使用reduce的变体

const getProduct = arr => arr。Reduce ((acc, value) => acc * value); const arrayWithExclusion = (arr, node) => 加勒比海盗。Reduce ((acc, val, j) => (node !== j ?)[…Acc, val]: Acc), []); const getproductwitheexclusion = arr => { Let result = []; 对于(设I = 0;I < arrr .length;I += 1) { 结果。推动(getProduct (arrayWithExclusion(加勒比海盗,我))); } 返回结果; };

左旅行->右和保持保存产品。称之为过去。- > O (n) 旅行右->左保持产品。称之为未来。- > O (n) 结果[i] =过去[i-1] *将来[i+1] -> O(n) 过去[-1]= 1;和未来(n + 1) = 1;

O(n)

def products(nums):
    prefix_products = []
    for num in nums:
        if prefix_products:
            prefix_products.append(prefix_products[-1] * num)
        else:
            prefix_products.append(num)

    suffix_products = []
    for num in reversed(nums):
        if suffix_products:
            suffix_products.append(suffix_products[-1] * num)
        else:
            suffix_products.append(num)
        suffix_products = list(reversed(suffix_products))

    result = []
    for i in range(len(nums)):
        if i == 0:
            result.append(suffix_products[i + 1])
        elif i == len(nums) - 1:
            result.append(prefix_products[i-1])
        else:
            result.append(
                prefix_products[i-1] * suffix_products[i+1]
            )
    return result