谜题..求解数组 X 中值的乘积

Question

你能帮我解决这个问题吗？

您有一个由 n 个整数组成的无序数组 X。查找包含 n 个元素的数组 M，其中 Mi 是 X 中除 Xi 之外的所有整数的乘积。您不能使用除法。您可以使用额外的内存。 （提示：有比 O(n^2) 更快的解决方案。）

基本解决方案 - O(n^2) 并且使用除法很容易。但我就是找不到比 O(n^2) 更快的另一种解决方案。

Answer 1

令 left[i] 为 X 中来自 1..i 的所有元素的乘积。令 right[i] 为 X 中来自 i..N 的所有元素的乘积。您可以按以下方式在 O(n) 中计算两者，无需除法：left[i] = left[i - 1] * X[i] 和 右[i] = 右[i + 1] * X[i];

现在我们将计算 M： M[i] = left[i - 1] * right[i + 1]

注意：left 和 < code>right 是数组。

希望很清楚：）

Answer 2

这是Python 中的解决方案。我用除法的简单方法与没有除法的困难方法进行比较。我能得到这份工作吗？

L = [2, 1, 3, 5, 4]

prod = 1
for i in L: prod *= i
easy = map(lambda x: prod/x, L)
print easy

hard = [1]*len(L)
hmm = 1
for i in range(len(L) - 1):
    hmm *= L[i]
    hard[i + 1] *= hmm
huh = 1
for i in range(len(L) - 1, 0, -1):
    huh *= L[i]
    hard[i - 1] *= huh
print hard

Answer 3

O(n) - http:// /nbl.cewit.stonybrook.edu:60128/mediawiki/index.php/TADM2E_3.28

两遍 -

 int main (int argc, char **argv) {
    int array[] = {2, 5, 3, 4};
    int fwdprod[] = {1, 1, 1, 1};
    int backprod[] = {1, 1, 1, 1};
    int mi[] = {1, 1, 1, 1};
    int i, n = 4;
    for (i=1; i<=n-1; i++) {
        fwdprod[i]=fwdprod[i-1]*array[i-1];
    }
    for (i=n-2; i>=0; i--) {
        backprod[i] = backprod[i+1]*array[i+1];
    }
    for (i=0;i<=n-1;i++) {
        mi[i]=fwdprod[i]*backprod[i]; 
    }
    return 0;
}

Answer 4

旧但非常酷，我自己在一次采访中被问到这个问题，并看到了几种解决方案，但这是我最喜欢的，取自
http://www.polygenelubricants.com/2010 /04/on-all-other-products-no-division.html

static int[] products(int... nums) {
       final int N = nums.length;
       int[] prods = new int[N];
       java.util.Arrays.fill(prods, 1);
       for (int // pi----> * <----pj
          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   ;
          System.out.println("pi up to this point is " + pi + "\n");
          System.out.println("pj up to this point is " + pj + "\n");
          System.out.println("prods[i]:" + prods[i] + "pros[j]:" +  prods[j] + "\n");
       }
       return prods;
    }

这是发生的事情，如果您为所有迭代写出 prods[i]，您将看到以下计算结果，

prods[0], prods[n-1]
prods[1], prods[n-2]
prods[2], prods[n-3]
prods[3], prods[n-4]
.
.
.
prods[n-3], prods[2]
prods[n-2], prods[1]
prods[n-1], prods[0]

因此每个 prods[ i] 被击中两次，一次是从头到尾，一次是从尾到头，这两次迭代都在累积乘积
向中心遍历，这样很容易看到我们会得到我们需要的东西，我们只需要小心，看看它错过了元素本身，这就是
这变得很棘手。关键在于

pi *= nums[i++], pj *= nums[j--]

for 循环条件本身，而不是主体，直到循环结束才发生
迭代。所以对于
产品[0]，
它从 1*1 开始，然后 pi 设置为 120，因此 prods[0] 错过了第一个元素
prods[1], 它是 1 * 120 = 120，然后 pi 被设置为 120*60
等等等等

Answer 5

O(nlogn) 方法：

int multiply(int arr[], int start, int end) {
    int mid;
    if (start > end) {
        return 1;
    }
    if (start == end) {
        return arr[start];
    }
    mid = (start+end)/2;
    return (multiply(arr, start, mid)*multiply(arr, mid+1, end));
}

int compute_mi(int arr[], int i, int n) {
    if ((i >= n) || (i < 0)) {
        return 0;
    }

    return (multiply(arr, 0, i-1)*multiply(arr, i+1, n-1));
}

Answer 6

这是我在Python中的解决方案：简单的方法，但计算成本可能很高？

def product_list(x):
ans = [p for p in range(len(x))]
for i in range(0, len(x)):
    a = 1
    for j in range(0, len(x)):
        if i != j:
            a = a*x[j]
        ans[i] = a
return ans