题目大意如下：
一排N（最大１Ｍ）个正整数+1递增，乱序排列，第一个不是最小的，把它换成-1，最小数为ａ且未知求第一个被
-1替换掉的数原来的值，并分析算法复杂度。
解题思路：
一般稍微有点算法知识的人想想就会很容易给出以下解法：
设 Sn = a + (a+1) + (a+2) + .........+ (a+n-1) = na +n(n-1)/2
扫一次数组即可找到最小值ａ，时间复杂度O(n)
设 S = 修改第一项后所有数组项之和, 求和复杂度为O(n)
则被替换掉的第一项为 a1=Sn-S-１
总的时间复杂度为 Ｏ(1)+O(n)+O(n) = O(n)
根据该算法写出程序很简单，就不写了
主要是解题过程中没有太考虑题目中给的１Ｍ这个数字，一面的时候被问到求和溢出怎么办？
当时我一想，如果要考虑溢出，必然是要处理大数问题，以前没有看到大数就头疼……所以立马想了个绕过大数加法的方法，如下：
设定另外一个数组b[N]
用 a, a+1,a+2....a+n-1依次分别减去原数组，得到的差放在该数组里，此求差过程复杂度为O(n)
对该数组各项求和即可得到Sn-S
面试官让证明一下我的设想，当时还没有给我纸和笔，用手在桌子上比划了一下没想出来，回来躺在床上想了一会就想出来了，也没什么难度：
相减求和后的数组，最差情况下应该是连续n/2个负数或者正数相加，如果不溢出，后面正负混合相加的话肯定不会溢出；这种情况下的最差特殊情况就是，原数列按照降序排列（除了第一项被替换掉了），而我们减时所用数列是增序排列。所得结果将是１个正数，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无关。
阅读(1690) | 评论(1) | 转发(1) |
