a)一个长度为n的数组a[0],a[1],...,a[n-1]。现在更新数组的名个元素,即a[0]变为a[1]到a[n-1]的积,a[1]变为a[0]和a[2]到a[n-1]的积,...,a[n-1]为a[0]到a[n-2]的积(就是除掉当前元素,其他所有元素的积)。程序要求:具有线性复杂度,且不能使用除法运算符。
分析:left[i]标示着a[i]之前的乘积,right[i]标示着a[i]之后的乘积,但不申请空间,那么a[i]=left[i]*right[i] 。不过,left的计算从左往右扫的时候得出,right是从右往左扫得出。因为就是当中某个元素a[i]的左边所有元素与右边所有元素的乘积,就这么简单。所以计算a[i]=left[i]*right[i]时,直接出结果。
b)两个数组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=a[0]a...a[i-1]aa[i+1]..*a[N-1]/a ,就是求:a[0]a[1]...a[i-1]*a[i+1]..*a[N-1]。只是我把a[i]左边部分标示为left[i],b[i]右边部分标示为right[i],而实际上完全不申请left[i],与right[i]变量,之所以那样标示,无非就是为了说明:除掉当前元素a[i],其他所有元素(a[i]左边部分,和a[i]右边部分)的积。