小程序

夜半的风

有一数组a[N]，有N-1个元素，其中有一个元素重复，用最优化的方法找出重复的元素，函数如下do_dupe(a[], N)。

crazyhadoop

数有范围吗？

luckysir

俺是普通人，只能给出普通方法，灌水呵呵

比如插入排序，在内层循环插入之前先折半查找有序部分

cokeboL

有范围的话就计数排序，复杂度为0(N)

夜半的风

回复 4# cokeboL


    怎么实现的？

cokeboL

回复 5# 夜半的风

近似：

1. #define MAX 100//范围
   
2. 
   
3. int a[N] = {.......};
   
4. int *p = malloc( 4*MAX );
   
5. for(i = 0; i < MAX; i++){
   
6.     p[i] = 0;
   
7. }
   
8. for(i = 0; i < N; i++){
   
9.     p[a[i]]++;
   
10.     if( p[a[i]] == 2 ){
    
11.         printf( "%d\n", p[a[i]] );
    
12.         break;
    
13.     }
    
14. }
    
15. 
    

复制代码

记得要free