异想天开

What's the true meaning of light, Could you tell me why

据说腾讯附加题

日期:2015-05-21 13:02:05
  
最后更新日期:2017-05-20 11:38:38
给定一个数组a[N],我们希望构造数组b [N],其中b[j]=a[0]*a[1]…a[N-1] / a[j],在构造过程中,不允许使用除法:要求O(1)空间复杂度和O(n)的时间复杂度;除遍历计数器与a[N] b[N]外,不可使用新的变量(包括栈临时变量、堆空间和全局静态变量等)
解析:
对于b[i],也就是a[0]...a[i-1] * a[i+1]...a[N-1]。即排除了位于对角线上的元素。如下图:

求b[i]也就是求a[i]左右两部分的乘积,那么可以先求出右边部分存放在b[i]里面,也就是b[i]=a[i+1]...a[N-1]。这里b[N-1]是最后才用到的变量,可以用做临时变量。
b[i] *= b[N-1]
b[N-1] *= a[i]
代码如下:
[code lang="cpp"]
#include<stdio.h>
const int N=5;
int a[N]={2,4,5,6,9};
int b[N];

int sovle()
{
b[N-1]=1;
for (int i=N-2; i>=0; --i){
b[i]=b[i+1]*a[i+1];
}

for (int i=0; i<N-1; ++i){
b[i] *= b[N-1];
b[N-1] *= a[i];
}
return 0;
}

int print()
{
for (unsigned int i=0; i<sizeof(a)/sizeof(a[0]); ++i){
printf("%d ",a[i]);
}
printf("\n");
for (unsigned int i=0; i<sizeof(b)/sizeof(b[0]); ++i){
printf("%d ",b[i]);
}
printf("\n");
return 0;
}

int main()
{
sovle();
print();
return 0;
}
[/code]