hash不错,但是要想找出个不冲突的数字hash函数比较难

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

1) N=10 a[N]={1,2,3,4,5,6,7,8,9,9} ?
2) N=10 a[N]={1,2,3,5,6,7,8,9,10,10} ?
3) N=10 a[N]={1,2,3,5,6,7,8,9,12,12} ?

如果是存放的是1到N-1的数，其中一个重复的话，是不是用哈希散列来解决？

#include <stdio.h>
#include <string.h>
int num[100000];
int main()
{
int i ,n ,a;
scanf("%d",&n);
memset(num,0,sizeof(num));
for(i=0;i < n;i++)
{
scanf("%d",&a);
num[a-1]++;
if(num[a-1]==2)
{
printf("%d\n",a);
}
}
}
不大清楚你说的,这样可以么?

你的程序在哪见过

楼上的这个算法不行吧，你不知道第几个数是重复的怎么把剩下的1到N-1 的加起来？

这样做可取，但不符合题意：注意时间复杂度是O(N)。

这个题目让我想到了NOIP普及组的 明明的随机数 这个题目：
大概就是，
给定一组数据，请将其排序（从小到大）并去除重复的数字。

用数学方法，同意福尔摩斯的算法。

门外汉 看不懂