题目大意如下:
一排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无关。
阅读(1699) | 评论(1) | 转发(1) |