今天去参加腾讯的笔试，最后一道附加题。
两个数组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)；
我自己的思路：通过分别拆分成[a[0],a[i-1]]和[a[i+1],a[N-1]]两部分来计算数组b的每个元素的值，即把a[i]的值扣除。
- b[0] = a[0];
- for(i = 1; i < N; ++i)
- {
- b[i] = b[0];//将b[i]赋值成a[0]~a[i-1]的乘积
- b[0] *= a[i];
- }
- b[0] = 1;
- for(i = N - 1; i > 0; ++i)
- {
- b[i] *= b[0];//在原来的乘积基础上，乘上a[i+1]~a[N-1]的乘积
- b[0] *= a[i];
- }
b[0] = a[0];
for(i = 1; i < N; ++i)
{
b[i] = b[0];//将b[i]赋值成a[0]~a[i-1]的乘积
b[0] *= a[i];
}
b[0] = 1;
for(i = N - 1; i > 0; ++i)
{
b[i] *= b[0];//在原来的乘积基础上，乘上a[i+1]~a[N-1]的乘积
b[0] *= a[i];
}
网上看到别人的思路。大体是一样的
- b[0] = 1;
- for (int i = 1; i < N; i++)
- {
- b[0] *= a[i-1];
- b[i] = b[0];
- }
- b[0] = 1;
- for (i = N-2; i > 0; i--)
- {
- b[0] *= a[i+1];
- b[i] *= b[0];
- }
- b[0] *= a[1];//最后赋b[0]的值，即后N-1项乘积
b[0] = 1;
for (int i = 1; i < N; i++)
{
b[0] *= a[i-1];
b[i] = b[0];
}
b[0] = 1;
for (i = N-2; i > 0; i--)
{
b[0] *= a[i+1];
b[i] *= b[0];
}
b[0] *= a[1];//最后赋b[0]的值，即后N-1项乘积
不过还是觉得我的代码好一些，呵呵~~