现在的位置: 首页 > 综合 > 正文

腾讯的一道笔试题

2014年02月08日 ⁄ 综合 ⁄ 共 363字 ⁄ 字号 评论关闭

两个数组a[N],b[N],其中A[N]的各个元素值已知,现给b[i]赋值,b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i];
要求:
1.不准用除法运算
2.除了循环计数值,a[N],b[N]外,不准再用其他任何变量(包括局部变量,全局变量等)
3.满足时间复杂度O(n),空间复杂度O(1)

 

先令b[i]=a[0]*a[1]*......a[i-1];

b[0]=1;

for(i=1;i<n;i++)

{

b[0]*=a[i-1];

b[i]=b[0];

}

然后再从后往前计算b[i]的值

for(i=n-2;i>0;i--)

{

b[0]*=a[i+1];//b[0]=a[n-1]*a[n-2]*a[n-3]*....a[i+1];

b[i]=b[i]*b[0];

}

b[0]=b[0]*a[1];

此时已经求出b[i]的值了。

抱歉!评论已关闭.