Chinaunix首页 | 论坛 | 博客
  • 博客访问: 963491
  • 博文数量: 128
  • 博客积分: 10012
  • 博客等级: 上将
  • 技术积分: 2050
  • 用 户 组: 普通用户
  • 注册时间: 2008-10-15 17:49
文章分类

全部博文(128)

文章存档

2011年(16)

2009年(57)

2008年(55)

分类: C/C++

2008-10-18 22:44:54

题目大意如下:

一排N(最大1M)个正整数+1递增,乱序排列,第一个不是最小的,把它换成-1,最小数为a且未知求第一个被

-1替换掉的数原来的值,并分析算法复杂度。

解题思路:

一般稍微有点算法知识的人想想就会很容易给出以下解法:

设 Sn = a + (a+1) + (a+2) + .........+ (a+n-1) = na +n(n-1)/2

扫一次数组即可找到最小值a,时间复杂度O(n)

设 S = 修改第一项后所有数组项之和,  求和复杂度为O(n)

则被替换掉的第一项为  a1=Sn-S-1

总的时间复杂度为 O(1)+O(n)+O(n) = O(n)

根据该算法写出程序很简单,就不写了

主要是解题过程中没有太考虑题目中给的1M这个数字,一面的时候被问到求和溢出怎么办?

当时我一想,如果要考虑溢出,必然是要处理大数问题,以前没有看到大数就头疼……所以立马想了个绕过大数加法的方法,如下:

设定另外一个数组b[N]

用 a, a+1,a+2....a+n-1依次分别减去原数组,得到的差放在该数组里,此求差过程复杂度为O(n)

对该数组各项求和即可得到Sn-S

面试官让证明一下我的设想,当时还没有给我纸和笔,用手在桌子上比划了一下没想出来,回来躺在床上想了一会就想出来了,也没什么难度: 

相减求和后的数组,最差情况下应该是连续n/2个负数或者正数相加,如果不溢出,后面正负混合相加的话肯定不会溢出;这种情况下的最差特殊情况就是,原数列按照降序排列(除了第一项被替换掉了),而我们减时所用数列是增序排列。所得结果将是1个正数,n/2-1个负数,n/2个正数;而且我们相当于用最大的n/2个数减去最小的n/2个数,差值之和最大,取到了最差情况,我们只考虑后面一半求和的情况即可(前面有个-1不方便处理):

S(n/2) = (n-1) + (n-3) + (n-5)+ .....+ 1    (n为奇数时最后一项是0,不影响我们讨论数量级计算溢出)

   = [(n-1)+1] * n/4 = n^2/4

题目中给定n最大为1M = 1024*1024

那么S(n/2)的最大量级为1024^4 = 2^40

而long long类型为64位,可以存放下该和,成功避免大数问题。

直接求和办法,一是和可能溢出,二是面试官要求把原始数组改称long long的话(即a可以也可能很大,求和时稍微加一下就会溢出)就得考虑大数求解了;而这种差值办法可以直接消掉a,求和只和n相关,和a无关。
阅读(1479) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

liubird2012-09-10 21:23:06

这题直接用异或就求出来了。
先把a到a+N-1求异或, 然后再和修改后的数组的除第一个数以外的所有数求异或,最后的结果就是被修改了的第一个数。
时间复杂度O(N), 空间复杂度O(1).