Chinaunix首页 | 论坛 | 博客
  • 博客访问: 498923
  • 博文数量: 59
  • 博客积分: 86
  • 博客等级: 民兵
  • 技术积分: 2141
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-30 20:57
个人简介

为今天而努力的人很平凡,为昨天而努力的人叫失败,只有为美好明天而战斗不止才叫精彩!

文章分类

全部博文(59)

文章存档

2015年(1)

2014年(3)

2013年(53)

2012年(2)

我的朋友

分类: C/C++

2013-04-20 21:36:59

题目:已知一个数组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特殊处理

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. int main()
  3. {
  4. int i, a[5]={1,2,3,4,5},b[5]={1,1,1,1,1};
  5. for(i=0;i<5;i++)
  6.  {
  7.     if(i!=0)b[i]=b[i-1];
  8.     b[i]*=a[i];
  9.  }
  10.  for(i=0;i<5;i++)
  11.   {
  12.      printf("%d ",a[i]);
  13.   }
  14.  printf("\n");
  15.  for(i=0;i<5;i++)
  16.  {
  17.      printf("%d ",b[i]);
  18.  }
  19.  printf("\n");
  20. for(i=4;i>=0;i--)
  21.  {
  22.      if(i==4)continue;
  23.      else a[i]*=a[i+1];
  24.  }
  25.  for(i=0;i<5;i++)
  26.  {
  27.      printf("%d ",a[i]);
  28.  }
  29.  printf("\n");
  30.  for(i=4;i>=0;i--)
  31.  {
  32.      if(i==4)
  33.      {
  34.          b[i]=b[i-1];
  35.      }
  36.  else if(i==0) 
  37.  {
  38.      b[i]=a[i+1];
  39.   }
  40.  else b[i]=b[i-1]*a[i+1]; 
  41. }
  42. for(i=0;i<5;i++)
  43.  {
  44.      printf("%d ",b[i]);
  45.  }
  46.  printf("\n");
  47. }


阅读(2783) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~