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

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

#include <stdio.h>

int do_dup(int a[],int n);
void main()
{
	int a[]={1,3,2,3};
	do_dup(a,4);
}

int do_dup(int a[],int n)
{
	int i;
	int *b=new int[n];
	for (i=0;i<n;i++)
		b[i]=0;
	for (i=0;i<n;i++)
	{
		if (b[a[i]]==0)
		{
			b[a[i]]=a[i];
		}
		else
			printf("%d\n",b[a[i]]);
	}
	delete []b;
	return 0;
}

上面的代码有个问题，就是当重复的数为0时，就找不出来。
不知道大家有没什么好的算法

34 个解决方案

#1

定义一个结构体啊。。、、

typedef struct int_node {
    int node_ref;
}node;


node node_array[n]...
每次赋值就是对node_ref ++

#2

代码有几个问题
1 当重复的数为0时，就找不出来。
2 动态分配内存大小，受数组最大元素值影响，当其中一个元素为100000，而数组只有4个元素的时候，造成浪费

#3

你的程序越界了.

#include <stdio.h>

int do_dup(int a[],int n,int m);
void main()
{
    int a[4]={1,3,2,5};
    do_dup(a,6,4);
}

int do_dup(int a[],int n,int m)
{
    int i;
    int *b=new int[n];
    for (i=0;i<n;i++)
        b[i]=0;
    for (i=0;i<m;i++)
    {
        if (b[a[i]]==0)
        {
            b[a[i]]=a[i];
        }
        else
            printf("%d\n",b[a[i]]);
    }
    delete []b;
    return 0;
}

#4

引用楼主 w66187564 的帖子:

数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o(N) 
...
就是当重复的数为0时，就找不出来。

第一,题目的叙述有点问题.
第二,如果数组中要存0,那你用于检测的b数组应初始化为负数之类的,不能用0.

#5

没必要分配内存

int do_dup(int a[],int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int k = a[i] - 1; k != i; )
        {
            if (a[i] == a[k])
                return a[i];

            a[i] = a[k];
            a[k] = k + 1;
            k = a[i] - 1;
        }
    }
    return 0;
}

#6

int a[]={1,3,2,3};
 for (i=0;i<n;i++)
    {
        if (b[a[i]]==0)//b[0]没有看到
        {
            b[a[i]]=a[i];
        }
        else
            printf("%d\n",b[a[i]]);
    }
回帖是一种美德！传说每天回帖即可获得 10 分可用分！

#7

帮你略改了一下，且这个程序只有在 数组元素全部是自然数&&数组最大元素为9999时能用：
#include <stdio.h>
#define N 10000

void del(int a[],int n);
void main()
{
    int a[]={1,3,2,3};
    del(a,4);
}
void del(int a[],int n)
{
    int i;
    int *record=new int[N];
    for (i=0;i<n;i++)
        record[i]=-1;
    for (i=0;i<N;i++)
    {
        if (record[a[i]]==-1)
        {
            record[a[i]]=a[i];
        }
        else
            printf("%d\n",record[a[i]]);
    }
    delete []record;
}

#8

 sorry, for (i=0;i <N;i++) 
    改为for (i=0;i <n;i++)  

#9

引用 5 楼 solar 的回复:

没必要分配内存 

C/C++ codeint do_dup(int a[],int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int k = a[i] - 1; k != i; )
        {
            if (a[i] == a[k])
                return a[i];

            a[i] = a[k];
            a[k] = k + 1;
            k = a[i] - 1;
        }
    }
    return 0;
}

时间复杂度必须为o(N) 

#10

引用 9 楼 w66187564 的回复:

引用 5 楼 solar 的回复:

没必要分配内存 

C/C++ codeint do_dup(int a[],int n) 
{ 
    for (int i = 0; i < n; i++) 
    { 
        for (int k = a[i] - 1; k != i; ) 
        { 
            if (a[i] == a[k]) 
                return a[i]; 

            a[i] = a[k]; 
            a[k] = k + 1; 
            k = a[i] - 1; 
        } 
    } 
    return 0; 
} 

时间复杂度必须为o(N)

这个时间复杂度就是o(N)。不要看到2层循环就以为不是O(N)

#11

1到N-1所有数字之和是固定的，可以有N*(N-1)/2得到，
再求出数组所有元素之和，
后者减去前者，即可得到重复的那个数字。

#12

是啊，这个题目出的有问题，应该为存放了1至N-1范围内共N个数。这样就可以用楼上的了

#13

引用 5 楼 solar 的回复:

没必要分配内存 
C/C++ code
int do_dup(int a[],int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int k = a[i] - 1; k != i; )//i = 0, a[0]= 1
        {
            if (a[i] == a[k]) //a[0] == a[0]
                return a[i];

            a[i] = a[k];
            a[k] = k + 1;
            k = a[i] - 1;
        }
    }
    return 0;
}

#14

－－－－－－－－－－－－－
        if (b[a[i]]==0)
        {
            b[a[i]]=a[i];
        }
－－－－－－－－－－－－－
改成
－－－－－－－－－－－－－
        if (b[a[i]]==0)
        {
            b[a[i]]=非0某常数;
        }
－－－－－－－－－－－－－
不就行了？

另：

引用 10 楼 solar 的回复:

引用 9 楼 w66187564 的回复:
引用 5 楼 solar 的回复:

没必要分配内存

C/C++ codeint do_dup(int a[],int n)
{
for (int i = 0; i  < n; i++)
{
for (int k = a[i] - 1; k != i; )
{
if (a[i] == a[k])
return a[i];

a[i] = a[k];
a[k] = k + 1;
k = a[i] - 1;
}
}
return 0;
}

时间复杂度必须为o(N)


这个时间复杂度就是o(N)。不要看到2层循环就以为不是O(N)

这个没看懂，能给详细讲解下么？

#15

改进以下,可以查找所有数了
int do_dup(int a[],int n)
{
    int i;
    bool *b=new bool[10];
    for (i=0;i<n;i++)
        b[i]=false;
    for (i=0;i<n;i++)
    {
        if (b[a[i]]==false)
        {
            b[a[i]]=true;
        }
        else
            printf("%d\n",a[i]);
    }
    delete []b;
    return 0;
}

#16

引用 5 楼 solar 的回复:

没必要分配内存
C/C++ codeintdo_dup(inta[],intn)
{for(inti=0; i<n; i++)
    {for(intk=a[i]-1; k!=i; )
        {if(a[i]==a[k])returna[i];

            a[i]=a[k];
            a[k]=k+1;
            k=a[i]-1;
        }
    }return0;
}

错的。

#17

7楼错了

#18

record[i]=-1;
应该改为record[a[i]]=-1;

#19

int do_dup(int a[],int N)    //未经调试 
 { 
      int sun = 0; 
      int sum2; 
      for(int i=0;i<N;++i) 
      { 
        Sum+=a[i]; 
      } 
      Sum2 = (1+N-1)*N/2; 
      Return (sum-sum2); 
 } 
这是我在别处看到的，，时间复杂度要注意

#20

这样修改一下就OK了——
int f(int a[],int n)
{
    int i;
int nNum = 0;
    int *b=(int*)malloc(sizeof(int)*10);
    for (i=0;i<n;i++)
        b[i]=0;
    for (i=0;i<n;i++)
    {
        if (b[a[i]]==0)
        {
            b[a[i]]=a[i];
if(i == n-1)
{
free(b);
return 0;
}
        }
        else
        {
nNum = b[a[i]];
free(b);
return nNum;
//printf("%d\n",b[a[i]]);
}
    }
    
return 0;
}

#21

引用 5 楼 solar 的回复:

没必要分配内存

C/C++ code
int do_dup(int a[],int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int k = a[i] - 1; k != i; )
        {
            if (a[i] == a[k])
                return ……

没看懂，但是我测试发现这个算法有问题。


int main(void)
{
 /* 此处添加你自己的代码 */
 int a[11] = {3,1,5,2,16,36,99,108,22,1,17} ;

  printf("%d",do_dup(a,11));
  getch();
  return 0;
}

这个出不来结果

#22

int k;
for(int i=1;i<N;i++)
{
k=~(k^a[i]);
}
求和可能会引起溢出 ，用同或运算

#23

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];
} //by X-Forever, 1030

#24

#23楼的程序测试过 求解释

#25

#23楼的程序有深度哦。
我发现整个过程实际上做了一个排序，重复那个数最后是放在了a[0]里，奇妙的是a[a[0]]正好是重复的那个数！

求如何设计这个算法的！！！

#26

#23楼的程序有深度  研究中

#27

23楼得也不对。。。

#28

19楼正解

#29

引用 23 楼 stonelk860122 的回复:

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];
} //by……

好算法，因为第二个重复的数字其位置肯定不会变化，而a[a[0]]正好可以访问到每一个位置的数据。

赞一个！

#30

int do_dup(int a[],int n)
{
    int i;
    int *b=new double[65535];
    for (i=0;i<65535;i++)
        b[i]=70000;
    for (i=0;i<n;i++)
    {
        if (b[a[i]]== 70000)
        {
            b[a[i]]=a[i];
        }
        else
            printf("%d\n",b[a[i]]);
    }
    delete []b;
    return 0;
}
将b定义成数组a中不可能出现的数就行了，a中数据是int型，所以b中全部初始化成一个大于65535的常数

#31

19楼正解
int sum_do_dup(int a[],int N) 
 {  
  int sum1 = 0;  
  int sum2 = 0;  
  for(int i=0;i<N;++i)  
  {  
  sum1+=a[i];  
  }  
  sum2 = (N-1)*N/2;  
  return (sum1-sum2);  
 }  

#32

引用 31 楼 kevinyao1985 的回复:

19楼正解
int sum_do_dup(int a[],int N) 
 {  
  int sum1 = 0;  
  int sum2 = 0;  
  for(int i=0;i<N;++i)  
  {  
  sum1+=a[i];  
  }  
  sum2 = (N-1)*N/2;  
  return (sum1-sum2);  
 }

sum2=（N-1）*（N-2）/2
只用1加到N-1

#33

引用 23 楼 stonelk860122 的回复:

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];
} //by……

这个算法有深度，研究中

#34

引用 5 楼 solar 的回复:

没必要分配内存
C/C++ code
int do_dup(int a[],int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int k = a[i] - 1; k != i; )
        {
            if (a[i] == a[k])
                return a[i];

 ……

这个也没看懂