腾讯2012年4月笔试题附加题
问题描述:两个数组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)
谈谈自己的解题思路吧,拿到这道题的时候,我首先注意到题目的3个要求:1.不准用除法2.不允许使用额外变量;3.o(n)的时间复杂度。由于不允许使用额外变量,所以我想到应该是在b[n]上做文章,结合不能用除法,我想到A^A=0,于是又A^A&1 = 1。再乘以剩下的各个乘子就得到b[i]。
本来以为到这里就结束了,后来发现这个方法有问题,因为这样只解决了不用除法做/a[i]的问题,没有解决如何乘上除了a[i]以外的数的问题。继续观察b[i]的结构发现,b[i]可以写成BaBb,其中Ba=a[0]*a[1]...*a[i-1],Bb=a[i+1]*a[i+2]...*a[n-1],自然的就联想到了分别从头和尾部遍历a[n]计算Ba,Bb的方法,话不多说,代码如下:
1 void foo(int a[],int b[],int n){
2 int i;
3 b[0] = 1;//用b[0]做辅助变量;
4 for(i = 1; i < n; i++)
5 {
6 b[0] *= a[i - 1];//从前往后乘得到Ba;
7 b[i] = b[0];
8 }
9 b[0] = 1;
10 for(i = n-2; i > 0; i--)
11 {
12 b[0] *= a[i + 1];//从后往前乘得到Bb;
13 b[i] *= b[0];
14 }
15 b[0] *= a[1];//不能忘记算出b[0];
16 for(i = 0; i < n; i++)
本内容试读结束,登录后可阅读更多
下载后可阅读完整内容,剩余3页未读,立即下载