我有两个数组inputArray，每个数组resultArray都有n元素。
任务是 in 的第 n 个元素resultArray应该是inputArray除inputArray( n-1elements in all) 的第 n 个元素之外的所有元素的乘法。
例如。inputArray={1,2,3,4}
那么resultArray={24,12,8,6}
这很容易......
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
if(i != j) resultArray[i] *= inputArray[j];
但问题是复杂度不应该超过O(n)
而且我们不允许使用除法。
我该如何解决这个问题？
在不破坏太多的情况下，您应该尝试使用两个变量来存储乘法的结果：第 i 个元素左侧和第 i 个元素右侧的乘法的累积结果。
您可以使用 DP 方法，如下所示：
vector<int> products(const vector<int>& input) {
int N = input.size();
vector<int> partial(N+1); // partial[i] = input[0]...input[i-1]. partial[0] = 1
partial[0] = 1;
for (int i = 0; i < N; ++i) partial[i+1] = input[i]*partial[i];
vector<int> ans(N);
int current = 1;
for (int i = N-1; i >= 0; --i) {
// current is equal to input[i+1]...input[N-1]
ans[i] = partial[i]*current;
current *= input[i];
}
return ans;
}
这种方法的一种可能用法是当您处理无法除以的事物时（例如，考虑与矩阵相同的问题）。
我使用 STL 向量完成了这个解决方案，但当然可以轻松地“翻译”代码以使用 C 数组。
main()
{
int i,l,r,x[5]={1,2,3,4,5},y[5]; // x is the initial array, y is the final array
int n = 5; // n be the size of the array, here already defined as 5
l = 1; // l is the product of the values of the left side of an index in x
r = 1; // r is the product of the values of the right side of an index in x
for (i=0 ; i<5 ; i++) y[i]=1; // initialising all y values to 1
for (i=0 ; i<5 ; i++)
{
y[i] = y[i]*l ;
y[n-i-1] = y[n-i-1]*r;
l = l*x[i];
r = r*x[n-i-1];
}
for (i=0; i<5; i++) printf("%d\n",y[i]);
}
你知道乘以奇数是可逆的——只用乘法吗？请参阅 Hacker's Delight，称为“精确除法”。正如那里解释的那样，这个技巧也可以扩展到偶数。所以你可以用几个乘法“除”第n个数字——因为这是家庭作业，我会留给你来看看如何。
Seeing Daniel Fleischman's answer, I decided I had to give my own implementation, since his has so many lines of code!
int i, buffer=1, result[n];
for(result[0]=1,i=1;i<n;i++) result[i] = result[i-1]*inputArray[i-1];
for(i=n-1,buffer=1;i>=0;buffer*=inputArray[i],i--) result[i]*=buffer;
Three lines of code (with all the fat cut out).