腾讯2013实习生招聘笔试附加题

题目：已知一个数组a[N]，构造一个数组b[N]，构造规则：b[i]=a[0]*a[1]*a[2]...a[N]/a[i];
要求：
1、不可以使用除法；2、时间复杂度为O(n)，空间复杂度为S(0)；　　3、除遍历使用的变量外，不可以使用其它变量；

思想：
从前往后扫一遍，然后从后往前再扫一遍。

也就是说，线性时间构造两个新数组，

B[i]=A[1]*A[2]*...*A[i]，A[i]=A[n]*A[n-1]*...*A[i]。于是，B[i]=B[i-1]*A[i+1]。

i=N和0特殊处理

#include<stdio.h>
int main()
{
int i, a[5]={1,2,3,4,5},b[5]={1,1,1,1,1};
for(i=0;i<5;i++)
 {
    if(i!=0)b[i]=b[i-1];
    b[i]*=a[i];
 }
 for(i=0;i<5;i++)
  {
     printf("%d ",a[i]);
  }
 printf("\n");
 for(i=0;i<5;i++)
 {
     printf("%d ",b[i]);
 }
 printf("\n");
for(i=4;i>=0;i--)
 {
     if(i==4)continue;
     else a[i]*=a[i+1];
 }
 for(i=0;i<5;i++)
 {
     printf("%d ",a[i]);
 }
 printf("\n");
 for(i=4;i>=0;i--)
 {
     if(i==4)
     {
         b[i]=b[i-1];
     }
 else if(i==0)
 {
     b[i]=a[i+1];
  }
 else b[i]=b[i-1]*a[i+1];
}
for(i=0;i<5;i++)
 {
     printf("%d ",b[i]);
 }
 printf("\n");
}