日期:2014-05-20  浏览次数:20683 次

某公司的一道笔试题的附加题,大家一起动动脑筋来看看
题目大概是这样的:有两个数组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++ 笔试

------解决方案--------------------
加了点注释
	public static void main(String[] args) {
//初始化条件参数
final int a[] = new int[]{2,3,4,5,6};
final int N = a.length;
int b[] = new int[N];
//设置b[0]的初始值为1,用于以后的累乘
//乘积被i拆成两部分,所以,可用两个循环完成。
b[0] = 1;
//计算前半部分
for(int i=1;i<N;i++){
b[i] = a[i-1] * b[i-1];
}
//计算后半部分,b[0]充当临时变量。b[0] = 1;
for(int i=N-2;i>0;i--){
b[0] *= a[i+1];
b[i] *= b[0];
}
}