据传说是MS/Google等等IT名企业的面试题：

有一组数字，从1到n，中减少了一个数，顺序也被打乱，放在一个n-1的数组里

请找出丢失的数字，最好能有程序，最好算法比较快

BTW1: 有很多种方法的哦，据说O(n)的方法就不止一种

BTW2: 扩展问题，如果丢失了2个数字呢？

BTW3: 一定要小心不要溢出，嗯，面试者有时候不会提醒你的

BTW4: 最好不要多申请n多空间

Update 一个很相近的题目：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？

来自Matrix67

题目：

1. 给你n个数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。
2. 给你n个数，其中有且仅有两个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。

答案：

1. 从头到尾异或一遍，最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质：两次异或同一个数，结果不变。再考虑到异或运算满足交换律，先异或和后异或都是一样的，因此这个算法显然正确。

2. 从头到尾异或一遍，你就得到了需要求的两个数异或后的值。这两个数显然不相等，异或出来的结果不为0。我们可以据此找出两个数的二进制表达中不同的一位，然后把所有这n个数分成两类，在那一位上是0的分成一类，在那一位上是1的分到另一类。对每一类分别使用前一个问题的算法。

确实是很牛的算法，特别是第二个

貌似比较经典的题了，这里列出一些我能想到的方法：
第一问：对于丢失一个数的情况：
1）用1+2+...+n减去当前输入数据的总和。时间复杂度：O(n) 空间复杂度：O(1) 【容易溢出】

2）用12...*n除以当前输入数据的总积。时间复杂度：O(n) 空间复杂度：O(1) 【容易溢出】

3）用1^2^...^n的结果在逐个异或当前输入数据。时间复杂度：O(n) 空间复杂度：O(1)

4）对输入数据排序，然后从头到尾遍历一次。时间复杂度O(nlogn) 空间复杂度O(1)

5) 对输入数据进行Hash，然后从头到尾遍历一次。时间复杂度O(n) 空间复杂度O(n)

第二问：对于丢失两个数的情况：
设丢失的两个数为x和y。
1）用1+2+...+n减去当前输入数据的总和可以得到x+y；用1^2+2^2+...+n^2减去当前输入数据的平方和可以得到x^2+y^2。联立两个方程可以得到x和y。时间复杂度：O(n) 空间复杂度：O(1) 【容易溢出】

2）用1+2+...+n减去当前输入数据的总和可以得到x+y；用12...n除以当前输入数据的总积可以得到xy。联立两个方程可以得到x和y。时间复杂度：O(n) 空间复杂度：O(1) 【容易溢出】

3）对输入数据排序，然后从头到尾遍历一次。时间复杂度O(nlogn) 空间复杂度O(1)

4）对输入数据进行Hash，然后从头到尾遍历一次。时间复杂度O(n) 空间复杂度O(n)

来个最笨的……应该是O(n)里最简单的吧……话说还是不会帖代码，粘贴过来就没格式了

#include <stdio.h>

#define N 10

int main()
{
        int a[N-1]={3,9,4,5,2,6,1,8,10}, missing=0;
        for(int i=1; i<=N-1; i++)missing+=i-a[i-1];
        missing+=N;
        printf("Missing Number: %d\n", missing);
        return 0;
}

来份不会溢出的（除非题干溢出）……支持找两个数，不过也就是O(n)……期待更快的算法

#include <stdio.h>
#include <string.h>

#define N 10
#define MISSNUM 2

int main()
{
        int a[N-MISSNUM]={3,9,5,2,6,1,8,10}, flag[N];
        memset(flag, 0, sizeof(flag));
        for(int i=0; i<=N-MISSNUM-1; i++)flag[a[i]-1]=1;
        for(int i=0; i<=N-1; i++)
                if(flag[i]==0)printf("Missing Number: %d\n", i+1);
        return 0;
}

再来份只要一点点空间(挖掉的数的空间)的好了……仍然O(n) [刚才那个算法有点乱，整理了下，放出，现在的思路很好理解了]

#include <stdio.h>
#include <string.h>

#define N 10
#define MISSNUM 2

void sit(int i, int a[], int b[]) //把第i个位置上的人赶到正确的座位去，直到来了正确的人
{
        while(a[i]!=i+1 && a[i]!=0){
                if(a[i]<=N-MISSNUM){ //a[i] <-> a[a[i]-1]
                        int t=a[i];
                        a[i]=a[a[i]-1];
                        a[t-1]=t;
                }else{ //a[i] <-> b[a[i]-(N-MISSNUM)-1]
                        int t=a[i];
                        a[i]=b[a[i]-(N-MISSNUM)-1];
                        b[t-(N-MISSNUM)-1]=t;
                }
        }
}

int main()
{
        int a[N-MISSNUM]={3,9,5,2,6,1,8,7}, b[MISSNUM];
        memset(b, 0, sizeof(b));

        for(int i=0; i<=N-MISSNUM-1; i++)
                sit(i, a, b);

        for(int i=0; i<=N-MISSNUM-1; i++)
                if(a[i]==0)printf("Missing Number: %d\n", i+1);
        for(int i=0; i<=MISSNUM-1; i++)
                if(b[i]==0)printf("Missing Number: %d\n",N-MISSNUM+i+1);

        return 0;
}

恩…这个。还能再简化吗？

int main(){
    int N=10,num[]={1,2,4,5,6,7,8,9,3},i,k=0;
    for(i=1;i<N;i++)
        k^=i^num[i-1];
    printf("%d",k^N);
}

接下来是丢两个数的…我用的py3…我说怎么程序总是通不过…原来py3把print改成了函数了

N = 10
num = [1,3,5,6,7,8,9,10]
print([i for i in range(1,N+1) if i not in num])

如果不允许开o(n)空间的话

丢两个数倒是有个时间是o(n)空间是o(logN)的算法…

很麻烦…和第k大数qsort修改算法差不多…

代码好长，不想写了…

……………………………………………………………………

听了同学的办法…我决定去死了…囧…

虽然现在的已经有了非常好的算法，但是我还是再多贴一份吧

使用位图：n个数字那就需要(n+1)/8个元素的unsigned char数组，如此扫描一遍原始数据更新相应的位，再扫描一遍char数组即可得到结果，如此不管是缺几个数，或者是对付有重复的数，均可迎刃而解。

关键算法：

 //更新：
    result[x>>3] |= x&0x07;// update：用更高效的x&0x07取代x%8; 
    //求解：
    for(i=0;i<((n+1)>>3);i++)
    {
       if(~result[i])
          break;
    }
    for(j=0;j<8;j++)
    {
       if(!(~result[i])^(0x1<<j))
          break;
    }
    x=(i+1)*8+j;

最优解法： 问题1：对全部许序列做亦或即可 时间复杂度O（n） 空间复杂度O（1）

问题2：建立一张hash表，hash[key]位置为空置1，发生碰撞置2。最后遍历一遍即可。 时间复杂度O（n） 空间复杂度O（n）

1.先用公式求1，n的数相加之和sequencesum
2.遍历数组一遍求和arraysum
3.缺失的数result=sequencesum - arraysum
时间复杂度 O(n) 空间复杂度O(1)

我用c实现的代码如下，答案不对？评论不能重排代码所以贴到这了 -》恩…这个。还能再简化吗？

#include <stdio.h>

unsigned short find_number(unsigned short * arr,unsigned short len)
{
    unsigned short k = 0;
    for(unsigned short i =1;i < len;i++)
        k ^= i ^ arr[i-1];
    return k ^len ;

}
int main(int argc,char*argv[])
{
    printf("%d\n",sizeof(unsigned short ));
    unsigned short arr[5] = {49995,49996,49997,50000,49999};
    unsigned short len = 6;
    unsigned short res = find_number(arr,len);
    printf("%d\n",res);
}

输出：
2
50002

我用c实现的代码如下，答案不对？评论不能重排代码所以贴到这了 -》恩…这个。还能再简化吗？

#include <stdio.h>

unsigned short find_number(unsigned short * arr,unsigned short len)
{
    unsigned short k = 0;
    for(unsigned short i =1;i < len;i++)
        k ^= i ^ arr[i-1];
    return k ^len ;

}
int main(int argc,char*argv[])
{
    printf("%d\n",sizeof(unsigned short ));
    unsigned short arr[5] = {49995,49996,49997,50000,49999};
    unsigned short len = 6;
    unsigned short res = find_number(arr,len);
    printf("%d\n",res);
}

输出：
2
50002

我觉得最简单的方法就是：

先求出1到n 的和，线性序列公式一步即得。然后求出数组中所有数字的和，然后用1到n的和减去数组中数字的和，结果就是缺的那个数字了。

我想代码就不需要了吧。太简单了。