N+1个从0到N的数找重复的那一个

Date:2012-12-02

题目:有N+1个数字，每个数字是0到N之间的一个数字(不包括N),其中有一个重复的。找到它.

我们用最快的时间做.复杂度最低为O(N)

象咱们程序员比较容易想到的方法:(假定N=10)

#include <stdio.h>

main()
{
    int data[11] = {
        1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
    }, i; 

    int a[10] = {0}; 
    for (i = 0; i < 11 && !a[data[i]]; a[data[i]] = 1, i++); 
    printf("%d %d\n", data[i], i);//print data & index
}

这种方法可以找到位置。

还有一个方法就是，全部数字的和减去0到N的和

#include <stdio.h>

main()
{
    int data[11] = {
        0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9
    }, i, a = 0; 

    for (i = 0; i < 11; a += data[i], i++); 
    for (i = 0; i < 10; a -= i, i++); 
    printf("%d\n", a);
}