面试题目一道，爽透了

数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o（N）函数原型：

int do_dup(int a[],int N)

79 个解决方案

#1

int do_dup(int a[], int N)
{
int i, num=0;
char * count = (int*)malloc(N*sizeof(char));
memset(count, 0, N*sizeof(char));
for (i=0; i<N; i++){
count[a[i]]++;
}
for (i=1; i<N; i++)
if (count[i] == 2) num = count[i];
return num;
}

#2

sorry
忘记释放内存了，还有个小错误

int do_dup(int a[], int N)
{
int i, num=0;
char * count = (int*)malloc(N*sizeof(char));
memset(count, 0, N*sizeof(char));
for (i=0; i<N; i++){
count[a[i]]++;
}
for (i=1; i<N; i++)
if (count[i] == 2) num = i;
free(count);
return num;
}

#3

iamliadai ()兄热终于公益事业啊！

#4

上面
if (count[i] == 2) num = i;
改成
if (count[i] == 2) {
num = i;
break;
}
会好些

#5

int test( int p[], int n)
{
int nResult = 0;
for ( int i = 0; i < n; i++)
{
nResult += p[i] - i;
}
return nResult;
}

#6

int test( int p[], int n)
{
      int nResult = 0;
      for ( int i = 0; i < n; i++)
      {
          nResult += p[i] - i;
      }
      return nResult;
}

#7

gfxiang(afu)兄的程序思路很好，相当于一个hash函数k = n,然后检测冲突。
但是题目说是N-1个数，并非说数值是1~N喔。但是数值范围不给出的话，好像很难在O(n)完成

#8

只要这N-1个数已知的话，不用Hash函数，在O(N)内这个重复的数都能找到。原理就是把A[0..N-1]的数加在一起，减去那已知的N-1个数字的和，就可以得到重复的那个数字。为简便起见，假定这个N-1个数就是从1开始的。程序如下：
int do_dup(int a[],int N)
{
int s1=0,s2=0;
for(int i=0; i<N; s1+=a[i],s2+=i++);
return s1-s2;
}

#9

更简短的程序是：
int do_dup(int a[],int N)
{
int n=0;
for( int i=0;i<N;n+=a[i]-i++ );
return n;
}

在vc6下，更可以写成：
int do_dup(int a[],int N)
{
for( int i=0, int n=0;i<N;n+=a[i]-i++ );
return n;
}

#10

学习

#11

a[i]-i++
这样写不怕出问题？

#12

gfxiang(afu) 兄的不错，乱改一下

int do_dup(int a[], int N)
{
    int i = 0;
    int num = 0;
    int * count = (int*)malloc(N*sizeof(int));
    memset(count, 0, N*sizeof(int));
    for (i = 0; i < N; i++)
    {
        if (2 == (++count[a[i]]))
        {
            num = a[i];
            break;
        }
    }
    free(count);
    return num;
}

#13

a[i]-i++
这样写不怕出问题？
～～～～～～～～～～～～～～～

此话怎么讲？
a[i]-i++ 语义很清晰啊，有啥问题？

#14

安全起见，可以写成这个样子
int do_dup(int a[],int N)
{
         int n=0;
for( int i=0;i<N;n+=a[i]-i,i=i+1 );
return n;
}

#15

a[i]-i++
这样写不怕出问题？
～～～～～～～～～～～～～～～

此话怎么讲？
a[i]-i++ 语义很清晰啊，有啥问题？

========

a[i]-i++确实有问题，因为a[i]和i++的计算顺序依赖编译器实现，改成你上面写的逗号表达式就没问题了。

#16

该回复被版主删除

#17

a[i]-i++ 有问题。
x1+x2+...+xn - (x1+x2+...+2*xi+...+xn) = xj-xi;(xi为重复元素，xj为未出现元素)。
你只能获得2个数的差，不能确定准确的元素。
应该再获取元素的平方和或者别的统计量，如
x1^2+x2^2+...+xn^2 - (x1^2+x2^2+...+2*xi^2+...+xn^2) = xj^2-xi^2;
两个等式求解才能得到准确的答案。

#18

申请的内存是连续的，如果数组的数不是连续的会有问题吧

#19

假设的是数组中存放的数是1到N-1，存放在一个N大小的数组中，有一个数重复了，题目的意思也是如此。
所以就是把(数组中N个数之和)-(1+2+...N-1)就是重复的那个数。

如果数组中存放的是任意的数字，只要知道他们是哪些数字，也可以同样的计算出来。

如果数组中存放的是任意的数字，并且不连续也不知道他们是哪些数字，除了hash，我就不知道有其他什么方法解决了。

#20

我晕
看得怎么这么迷茫呢？？

#21

虾米

#22

楼主难到和我去了同一个公司面试????

#23

int do_dup(int a[],int N)
{
//设一个很大的数组保证这个数组的容量大于a中最大的数
int i;
bool b[MAX_A]={false};
for( i = 0;  i < N  ; ++ i)
{
   if(b[a[i]])
      break;
   b[a[i]] = true;
}  
return a[i];
}

#24

LZ应该没有把问题表达清楚,如果没猜错的话，应该是这样的。
a[0] + ... + a[N-1] - n*(1 + N -1)/2 = 结果.

#25

ls正解

#26

面试题目一道，
爽透了？
========
lz。。。

#27

unsigned int 
find(unsigned int* array, unsinged int n)
{
    unsigned int total = 0;
    unsigned int real = 0;
    for (unsigned int i = 0; i < n; i++)
    {
       total += i;
       real += array[i];
    }
    return total - real;
}

#28

存放了1至N-1个数.
又不是存的数值为1至N-1..上面的好多错了

#29

MARK

#30

借花献佛
int do_dup(int a[], int N)
{
int i, num=0;

int len = N*sizeof(int);
char* count = (char*)malloc(len) ;
memset(count, '0', len);

    for (i = 0; i < N; i++)
    {
        if ('2' == ++count[a[i]])
        {
            num = a[i];
            break;
        }
    }

free(count);
return num;
}

#31

应该是存储的数值为1～N－1吧

很简单
先算出1+2+3+...+N-1=sum

再算出数值中元素的总和为sum_array = a[0] + a[1] + a[2] + ... + a[n-1]

用sum_array - sum 就是重复的那个数

#32

mark, 学习学习.

#33

但是有个大问题就是如何防止溢出呢？


有可能这个ｓｕｍ很大啊，　很正常的．

#34

for(int i=0; i<N; i++)
{
   if(a[a[i]]<0)
   {
     a[i]这个数重复了，结束
   }
   a[a[i]] *= -1;
}

#35

修改刚才,索引要去绝对值
for(int i=0; i<N; i++)
{
   if(a[ abs(a[i]) ]<0)
   {
     a[i]这个数重复了，结束
   }
   a[a[i]] *= -1;
}

#36

不要意思，还有个错，索引要从0开始，呵呵.
for(int i=0; i<N; i++)
{
   if(a[ abs(a[i])-1 ]<0)
   {
     a[i]这个数重复了，结束
   }
   a[ abs(a[i]) -1] *= -1;
}
不过LZ要谢我，帮你顶了这么多次

#37

to:winux(放牛娃) 
例如：
N = 2,a[0] = 10,a[1] = 10;
会是什么结果？

#38

用hash表可以查出任意相同的，不过数不能太大阿

#39

我的理解
存放了1至N-1个数

是1到N-1这N-1个数只是顺序不定。

如果排序的话，就能得到1,2,3,3,4,...,N-1，其中3出现两次 ，3就是要找出来的那个重复的数

#40

hash的话，得保证不同的值不会冲突，只有相同的值才会冲突，这样只能用一个单调函数作为哈希函数，这样得对取值有限制，如果这N-1个数里面有一个10000000000000000，怎么办？

#41

貌似讨论的还是数学方面的问题……

#42

a[N]数组，数组中元素的取值：1至N-1,这些数中只有一个出现2次，其余出现一次，他们刚好凑够N个数？
如果这样的话，很简单，扫描一便就知道了，设未知的重复数值为x
 则所有数的和为1+2+...+N-1+x = (N-1)*(1+N-1)/2  + x =(N-1)*N/2 + x(等差数列)
因为N已知,扫描一遍实际的数,把和加起来,减去上面式子中除去x部分的值就得到了x
#define N 100
int main( int a[N])
{
  int sum=0;
  int partsum=(N-1)*N/2;
  for(int i=0;i<N;i++)
  {
    sum=sum+a[i];
   }
  return (sum-partsum);
}
如果这些数是没有规律的，任意数，我还没想到该怎么弄。

#43

溢出问题怎么考虑?

#44

int x = 0xffffffff; 
int z = x + 2; // 0x00000001
int w = z - x; // 0x00000002
假设sum(1:N-2) = 0xffffffff; 
a[N - 1] = 0x00000002;
sum(1:N-1) = 0x00000001;
sum(1:N-1) - sum(1:N-2) = 0x00000002
能不能说明a[N - 1]就是那个重复的数啊，不能吧。

#45

MARK

#46

最大的数可以考虑到2147483647，因为题目中是int a[]，范围是-2147483648~2147483647

#47

我想楼主说的应该是 a[0] - a[n-1] , 里面的数都是未知的, 唯一知道的就是这N 个数里面有两个是相同的. 各位有什么好办法吗?

#48

int do_dup(int a[],int N)
{
    int temp;
    //a[0]为监视哨
    while (a[0]!=a[a[0]])
    {
        temp = a[0];
        a[0] = a[temp];
        a[temp] = temp;
    }
    return a[0];
}

#49

这个题目就是一个数组内有：1 - (n-1)的连续整数和一个整数K（1<=K<=n-1）,他们在数组存放位置是任意的。
那么就有: K = 数组所有元素的和 - (1到n-1的等差数集合的和)

int do_dup(int a[],int N)
{    
     long long Sum = N*(N-1)/2; //用long long防止求和溢出
     long long SumArray = 0;
     for(int Index = 0; Index < N; Index++)
     {
          SumArray+= a[Index];
     }
     return (int)(SumArray - Sum); //这里差值一定在-2^31- 2^31 范围内
}

#50

对了，上面忘记判断 assert(N >= 2); 了  ._.!

int do_dup(int a[],int N)
{    
     assert(N >= 2);  
     long long Sum = N*(N-1)/2; //用long long防止求和溢出
     long long SumArray = 0;
     for(int Index = 0; Index < N; Index++)
     {
          SumArray+= a[Index];
     }
     return (int)(SumArray - Sum); //这里差值一定在-2^31- 2^31 范围内
}