题目

==============题目如下====================

简述:n个空间,存放a到a+n-1的数,位置随机且数字不重,a为正且未知.
现在第一个空间的数被误设置为-1.
（说明:已经知道被修改的数不是最小的.）

例子:n=6, a=2,原始的串为5, 3, 7, 6, 2, 4.现在被别人修改为-1, 3, 7, 6, 2, 4.
现在希望找到5.

限制:n不超过1M,现在希望找出这个数,并且实现尽量快.

要求:完成函数(实现尽可能高效)
unsigned int find_lost(const int* source, const length)
source为数组起址,length为长度.

给出思路(文字描述),完成代码,并且分析你算法的时间复杂度。

============我是题目与分析的分界线=====================================

其实这里把第一个空间的数换成任意数都无所谓啦。。。 我下面分析里面的A[0]就是要求的拿掉的数。

从A[1]起遍历，例子中从3起遍历。
可以确定：
（1）xor=A[1]^...^A[n-1]
（2）最小值a（题目说被修改的数不是最小的）

   A[0]^xor
=A[0]^A[1]^...^A[n-1]
=a^(a+1)^...^(a+n-1)

=> A[0]=xor^a^(a+1)^...^(a+n-1)

又[1^2...^(a-1)] ^ [a^(a+1)^...^(a+n-1)] =1^...^(a+n-1)
则 a^(a+1)^...^(a+n-1) = [1^...^(a+n-1)] ^   [1^2...^(a-1)]

因此：A[0]=xor^[1^...^(a+n-1)]^[1^2...^(a-1)]

其中，以下公式可是俺辛辛苦苦找规律找来的哇，可根据数学归纳法证明^_^。

S(N)=1^2^3^...^N，设k=0,1,...
当N=4k+1时，S(N)=1
当N=4k+2时，S(N)=S(N-1)^N=S(4k+1)^N=1^N=N+1（位运算快or加法快）
当N=4k+3时，S(N)=S(N-1)^N=N^N=0
当N=4k+4时，S(N)=S(N-1)^N=0^N=N

这个公式可是很实用的哇，很多什么连续的整数的少一个数、多一个数啥的笔试面试题都可用它试试。

再看这道题：网上有人还说用64位求和，那问题扩展到DWORDLONG型就照样溢出。

============我是分析与代码的分界线====================================

#include

//返回1^2^3^...^n
inline unsigned int xor_sum(unsigned int n)
{
    unsigned int t=n%4;
    if(1==t) return 1;
    else if(2==t) return 1^n;
    else if(3==t) return 0;
    else return n;
}

unsigned int find_lost(const unsigned int* source, const int length)//遍历一次，显然O(length)
{
    unsigned int xor=0;
    unsigned int a=(unsigned int)-1;
    for(int i=1;i    {
        xor^=source[i];
        if(source[i]    }
    return xor^xor_sum(a-1)^xor_sum(a+length-1);
}

unsigned int A[6]={-1,3,7,6,2,4};

int main(int argc, char* argv[])
{
    printf("缺少的数为：%d\n",
        find_lost(A,sizeof(A)/sizeof(*A))
        );   
return 0;
}