我在一次工作面试中被问到这个问题,我想知道其他人是如何解决这个问题的。我最擅长使用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中使用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(加勒比海盗,我))); } 返回结果; };

其他回答

下面是Ruby中的一行程序解决方案。

全国矿工工会。映射{|n| (num - [n]).inject(:*)}

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)

预先计算每个元素左右两边数字的乘积。 对于每个元素,期望值都是它相邻元素乘积的乘积。

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

结果:

$ ./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

(更新:现在我仔细看,这使用与Michael Anderson, Daniel Migowski和上面的聚基因润滑剂相同的方法)

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

我想出了这个解决方案,我发现它很清楚,你觉得呢!?

技巧:

使用以下方法:

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

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