用 O(n) 替换数组元素，将数组元素替换为整个数组中所有其他元素的倍数

Question

我有一个数组arr = [3,4,2,5,6,8,2].数组
中的每个元素都必须替换为数组中所有其他元素的倍数。
例如index=0，值3必须替换为4*2*5*6*8*2和index=3，值5必须替换为3*4*2*6*8*2。
这必须在O(n)完成.
我有dequeue和stack的解决方案，但我最终进行了 n*n-1 次迭代，导致O(n^2).有什么帮助吗？

Answer 1

首先，计算此数组的总乘积。 然后，对于数组中的每个元素，除以该值并将结果分配给其位置。 所以总乘积在 O(n( 中完成，赋值也在 O(n( 中完成。

=> ALG： O(2*n( = O(n(

Answer 2

1. 形成两个数组：左边一个累积乘积，右边一个累积。它们都可以用 O(2*n( 构造。
2. 将元素的左累积乘积乘到左侧，然后乘以右侧的右累积乘积。这需要 O(n(。

像这样：

leftCumulative[1]=1;
for(j=2;j<=n;++j) leftCumulative[j]=leftCumulative[j-1]*arr[j];
rightCumulative[n]=1;
for(j=n-1;j>=1;--j) rightCumulative[j]=arr[j]*rightCumulative[j+1];
arr[1]=rightCumulative[2];
arr[n]=leftCumulative[n-1];
for(j=2;j<=n-1;++j) arr[j]=leftCumulative[j-1]*rightCumulative[j+1];

可以使用更少的额外内存，并使循环更干净，但这解决了所述问题。如果乘法是非交换的，它甚至有效！

Answer 3

使用 java，

int[] arr = {3, 4, 2, 5, 6, 8, 2};
int wholeProduct = arr[0];   //  wholeProduct = arr[0] * arr[1] * ... * arr[n-1]
for(int i=1; i<arr.length; i++)
wholeProduct *= arr[i];
for(int i=0; i<arr.length; i++) 
arr[i] = wholeProduct/arr[i];

与@Lecagy描述的技术相同。

请注意，当包含许多元素时，整个产品可能不包含结果，您需要将类型更改为long或BigInteger。