Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4842688
  • 博文数量: 930
  • 博客积分: 12070
  • 博客等级: 上将
  • 技术积分: 11448
  • 用 户 组: 普通用户
  • 注册时间: 2008-08-15 16:57
文章分类

全部博文(930)

文章存档

2011年(60)

2010年(220)

2009年(371)

2008年(279)

分类: LINUX

2009-08-19 18:08:43

长度为 N 的整数数组,找出其中任意(N-1)个乘积最大的那一组,只能用乘法,不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析,不要求写程序。

    令这 N 个数的乘积为 P
    1)
如果 P<0,则剔除其中最大的负整数即可;
    2)
如果 P=0
        2.1)
若这 N 个数中有且仅有一个为“0”。若其他数之积为正,则剔除“0”;否则剔除任意一个非零数;
        2.2)
若这 N 个数中至少有两个为“0”,则随便剔除一个数均可;
    3)
如果 P>0,如果有正数,则剔除其中最小的正整数即可;否则,剔除最小的负整数。

   
时间复杂度:遍历数组,获得正整数个数 cp,负整数个数 cn0 的个数 cz,需要 O(N) 时间;找被剔除的数最坏情况下需要 O(N) 时间。输出结果需要 O(N) 时间。因此,时间复杂度为 O(N)

   
空间复杂度:数组存储需要 O(N) 空间,cp, cn, cz 和被剔除的数的下标各需要 O(1) 空间。因此,空间复杂度为 O(N)

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