加分题 :
给定一个数组a[N],我们希望构造数组b
[N],其中b[j]=a[0]*a[1]…a[N-1] / a[j],在构造过程中,不允许使用除法;
要求:
O(1)空间复杂度和O(n)的时间复杂度;
除遍历计数器与a[N] b[N]外,不可使用新的变量(包括栈临时变量、堆空间和全局静态变量等)
解析:
由题意知:b[j] = a[0]*....*a[j-1] * a[j+1]*....*a[N-1],那么可以把b[j] 分成两部分再做计算,
b[j] = a[0]*....*a[j-1] ; 在后面再做 b[j] = b[j]*
a[j+1]*....*a[N-1] ;
在前半部分a[0]*....*a[j-1],可以找到一个递推式
b[j] = b[j-1]* a[j-1] ;
同样在后面一个式子a[j+1]*....*a[N-1]也可以找到一个递推式: b[j] = b[j+1] * a[j+1] ,当然要注意哦,前面的结果是后面的输入,所以要中间变量过度一下
在做之前必须要有一个变量,我可以随便选一个,一般来说选 b[0] ,或是b[n-1] ,用完它们后,再把它们的计算回去,就OK了
那么这样一个,复杂度 只有 kN ,虽然不是 K, 但是复杂度也能是 O(N) ,所以符合题意;
具体代码如下:
#include <iostream> void clac( int *const a, int * const b,int N){ int i=0; b[0] = 1; for(i=1;i<N;i++){//计算 b[i] = b[i-1]*a[i-1] ; } b[0] = 1 ; for(i=N-1;i>=1 ;i--){ b[i] *= b[0]; b[0] *= a[i] ; } } int main(int argc,char **argv){ enum{N=1024}; int a[N] ,b[N]; //cin >> a ; clac(a,b,N); return 0; }