某公司的一道笔试题的附加题,大家一起动动脑筋来看看
题目大概是这样的:有两个数组a[N],b[N],求构造b[i]=a[0]*a[1]*a[2]*...a[N-1]/a[i],
要求:
1、不能使用除法。
2、空间复杂度O(1),时间复杂度O(n)。
3、除循环计数器和a[N]、b[N],不能使用其他变量。
用主流语言实现,讲讲想法。
大家动动脑筋,求大神指教,最好有代码。 算法 java c/c++ 笔试 编程语言
[解决办法]
或者这个更好
#define N 10
b[0] = 1;
for (int i = 1; i < N; ++i)
{
b[i] = b[i-1] * a[i-1];
}
for (int i = N - 1; i > 0; --i)
{
b[i] *= b[0];
b[0] *= a[i];
}