关于查找的C题
数组a[N]中，存放了N到N-1个数，其中某个数重复一次，写一个函数找出重复的数字，时间复杂度为O(N)，函数原型：
int do_dup(int a[], int N).请各位大侠指教。
int do_dup(int a[], int N)
{
char b[N]={0};
int i;
for(i=0;i <N;i++)
if(b[a[i]]) return a[i];
else b[a[i]]=1;
return -1;//not found
}
楼上正解。
用标记数组即可
如果存放的数是0~N-1，楼上的方法可行。
否则只能采取位图的方式，才能达到O(N)。即用一个bit的值来标记某个数是否出现。这样1个字节有8个bit。需要多少个bit，取决于最大最小值在数轴上覆盖的范围。
学习！
如果实现不知道范围呢？
这样，需要用到map或者hash之类的数据结构，时间复杂度会变成Nlog2N
int do_dup(int a[], int N)
{int i,j;
for(i=0;i <N-1;i++)
for(j=i+1;j <N;j++)
if(a[i]==a[j])
return a[i];}
二楼代码运行之后，输出结果是1，没找出错在什么地方。
void main()
{
int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 8, 9};
int num;
num = do_dup(arr, 10);
printf("%d\n", num);
}
位图可以，但是受空间限制很大。可以考虑改�
相关问答：
QQ群 29152388
友情UP
帮顶
up
帮up
up 支持！
up jf
...难道有分..?
up up up
希望有得加分，哈哈。
支持，我加了，希望楼主能加我，共同学习哈
加了。
顶上，每天收获一点，支持� ......
以前在VC里面建一个工程，都只用一个 .c 文件，昨天在一个工程里用了两个 .c文件了，遇到问题了，请大家指点。比如：
File1.c Fil ......
C\C++如何计算函数的导数,本人新手，想写个程序，但是不知道如何下手，还望高手指点一二，谢过。
这个……
跟函数的具体形式有关吧，难道你想编出个“万能”的求导函数？
俺上学时想过自动推导公式，后来 ......
大家好！我是一位C爱好者，向大家请教下，C程序员可好找工作？公司用C干些什么？
无所谓好不好找工作，一般通信、系统、嵌入式、硬件方面用的多，而且由于C的底层特性，学会后在学其他的会比较容易
不管用什么语 ......
