随笔 - 100  文章 - 50  trackbacks - 0
<2014年3月>
日一二三四五六
2324252627281
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

收藏夹

我收藏的一些文章!

搜索

  •  

最新评论

阅读排行榜

评论排行榜

找出数组中唯一重复的数

题目：

数组a[N]，1至N-1这N-1个数存放在a[N]中，其中某个数重复一次。写一个函数，找出被重复的数字。

方法一：异或法。

数组a[N]中的N个数异或结果与1至N-1异或的结果再做异或，得到的值即为所求。

  • 设重复数为A，其余N-2个数异或结果为B。 
  • N个数异或结果为A^A^B 
  • 1至N-1异或结果为A^B 
  • 由于异或满足交换律和结合律，且X^X = 0  0^X = X; 
  • 则有 
  • (A^B)^(A^A^B)=A^B^B=A 

代码：

 

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <math.h>  
  4. #include<time.h>  
  5. void xor_findDup(int * a,int N)    
  6. {    
  7.     int i;    
  8.     int result=0;    
  9.     for(i=0;i<N;i++)    
  10.     {    
  11.         result ^= a[i];    
  12.     }    
  13.       
  14.     for (i=1;i<N;i++)     
  15.     {    
  16.         result ^= i;    
  17.     }    
  18.       
  19.     printf("%d\n",result);    
  20.       
  21. }    
  22.  
  23.  
  24.  
  25. int main(int argc, char* argv[])    
  26. {    
  27.     int a[] = {1,2,1,3,4};    
  28.     xor_findDup(a,5);    
  29.     return 0;    
  30. }   

 方法二：数学法。

对数组的所有项求和，减去1至N-1的和，即为所求数。

 

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <math.h>  
  4. #include<time.h>  
  5. void xor_findDup(int * a,int N)    
  6. {    
  7.     int tmp1 = 0;  
  8.       
  9.     int tmp2 = 0;  
  10.       
  11.     for (int i=0; i<N-1; ++i)  
  12.           
  13.     {  
  14.           
  15.         tmp1+=(i+1);  
  16.           
  17.         tmp2+=a[i];  
  18.           
  19.     }  
  20.     tmp2+=a[N-1];  
  21.     int result=tmp2-tmp1;     
  22.     printf("%d\n",result);    
  23.       
  24. }    
  25.  
  26.  
  27.  
  28. int main(int argc, char* argv[])    
  29. {    
  30.     int a[] = {1,2,4,3,4};    
  31.     xor_findDup(a,5);    
  32.     return 0;    
  33. }   

对于求和，可以直接根据公式定义一个宏。#define sum(x)  (x*(x+1)/2)
 

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <math.h>  
  4. #include<time.h>  
  5. #define sum(x)  (x*(x+1)/2)   
  6. void xor_findDup(int * a,int N)    
  7. {    
  8.     int tmp1 = sum((N-1));//注意N-1要加括号     
  9.     int tmp2 = 0;  
  10.       
  11.     for (int i=0; i<N; ++i)       
  12.     {             
  13.         tmp2+=a[i];   
  14.     }  
  15.     int result=tmp2-tmp1;     
  16.     printf("%d\n",result);        
  17. }    
  18.  
  19. int main(int argc, char* argv[])    
  20. {    
  21.     int a[] = {1,2,4,2,3};    
  22.     xor_findDup(a,5);    
  23.     return 0;    
  24. }   

 方法三：标志数组法

申请一个长度为n-1且均为'0'组成的字符串。然后从头遍历a[n]数组，取每个数组元素a[i]的值，将其对应的字符串中的相应位置置1，如果已经置过1的话，那么该数就是重复的数。就是用位图来实现的。 如果考虑空间复杂度的话，其空间O（N）

 

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <math.h>  
  4. #include<time.h>  
  5. #define sum(x)  (x*(x+1)/2)   
  6. void xor_findDup(int * arr,int NUM)    
  7. {    
  8.     int *arrayflag = (int *)malloc(NUM*sizeof(int));      
  9.     int i=1;  
  10.       
  11.     while(i<NUM)  
  12.     {  
  13.         arrayflag[i] = false;  
  14.         i++;  
  15.     }     
  16.       
  17.     for( i=0; i<NUM; i++)         
  18.     {         
  19.         if(arrayflag[arr[i]] == false)            
  20.             arrayflag[arr[i]] = true;          // 置出现标志  
  21.           
  22.         else      
  23.         {   
  24.             printf("%d\n",arr[i]);  
  25.             return ; //返回已经出现的值  
  26.         }  
  27.           
  28.      }    
  29. }    
  30.  
  31. int main(int argc, char* argv[])    
  32. {    
  33.     int a[] = {1,3,2,4,3};    
  34.     xor_findDup(a,5);    
  35.     return 0;    
  36. }    

 方法四：固定偏移量法

a[N]，里面是1至N-1。原数组a[i]最大是N-1，若a[i]=K在某处出现后，将a[K]加一次N，做标记，当某处a[i]=K再次成立时，查看a[K]即可知道K已经出现过。该方法不用另外开辟O(N)的内存空间，但是在查重之后要将数组进行恢复。

 

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <math.h>  
  4. #include<time.h>  
  5. void xor_findDup(int * arr,int NUM)    
  6. {    
  7.     int temp=0;       
  8.     for(int i=0; i<NUM; i++)          
  9.     {  
  10.           
  11.         if(arr[i]>=NUM)           
  12.             temp=arr[i]-NUM;            // 该值重复了，因为曾经加过一次了        
  13.         else              
  14.             temp=arr[i];          
  15.                   
  16.         if(arr[temp]<NUM)         
  17.         {         
  18.             arr[temp]+=NUM; //做上标记            
  19.         }  
  20.           
  21.         else              
  22.         {             
  23.             printf("有重复 %d\n",temp);              
  24.             return;           
  25.         }         
  26.     }  
  27.               
  28.     printf("无重复");  
  29.     return ;   
  30. }    
  31. void clear(int *data,int num)//清理数据  
  32. {  
  33.     for(int i=0;i<num;i++)  
  34.     {  
  35.         if(data[i]>num)  
  36.             data[i]-=num;  
  37.     }  
  38.  
  39. }  
  40. int main(int argc, char* argv[])    
  41. {    
  42.     int a[] = {2,4,3,4,1};    
  43.     xor_findDup(a,5);    
  44.     clear(a,5);  
  45.     return 0;    
  46. }    

 方法五：符号标志法

上个方法出现后是加N，也可以出现后加个负号，就是符号标志法。

 

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <string.h>  
  4. #include <math.h>  
  5. #include<time.h>  
  6.  
  7. void xor_findDup(int * arr,int NUM)    
  8. {         
  9.     int temp=0;          
  10.     for(int i=0; i<NUM; i++)        
  11.     {                    
  12.         if(arr[i]<0)     
  13.             temp=0-arr[i];  // 该值重复了，因为曾经加过一次了     
  14.         else                           
  15.             temp=arr[i];                
  16.         if(arr[temp]>0)             
  17.         {                    
  18.             arr[temp]=0-arr[temp]; //做上标记        
  19.         }                
  20.         else              
  21.         {               
  22.             printf("有重复 %d\n",temp);      
  23.             return;               
  24.         }            
  25.     }                
  26.     printf("无重复");    
  27.     return ;    
  28.  }     
  29.  void clear(int *data,int num)//清理数据  
  30.  {     
  31.      for(int i=0;i<num;i++)     
  32.      {        
  33.          if(data[i]<0)           
  34.              data[i]=0-data[i];     
  35.    }     
  36. }    
  37.  int main(int argc, char* argv[])    
  38.  {        
  39.      int a[] = {3,2,1,4,1};       
  40.      xor_findDup(a,5);     
  41.      clear(a,5);      
  42.      return 0;    
  43.  }      

以上的方法对数组元素的值的范围是有限制的，如果数组元素的值不是在1至N-1范围时，可以先求出数组元素的最大值。

 

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <string.h>  
  4. #include <math.h>  
  5. #include<time.h>  
  6.  
  7. int  do_dup_mal(int arr[], int n, int *pre, int *back)  
  8. {  
  9.     int MAX = -1;  
  10.     int i = 0;  
  11.     int sameVal = -1;  
  12.     *pre = *back = -1;  
  13.       
  14.     for (int j=0; j<n; j++)  
  15.     {  
  16.         if (arr[j] > MAX) MAX = arr[j];//找出数组中的最大数  
  17.     }  
  18.       
  19.     char *arrayflag = new char[MAX+1] ;  
  20.     if (NULL == arrayflag)  
  21.         return -1;  
  22.     memset(arrayflag, 0, MAX+1 ); // '\0' == 0  
  23.     for(i=0; i<n; i++)  
  24.     {  
  25.         if(arrayflag[arr[i]] == '\0')  
  26.             arrayflag[arr[i]] = '\1'; // 置出现标志  
  27.         else 
  28.         {  
  29.             sameVal = arr[i]; //返回已经出现的值  
  30.             *back = i;  
  31.             break;  
  32.         }  
  33.     }  
  34.     delete[] arrayflag;  
  35.     if (i < n)  
  36.     {  
  37.         for (int j=0; j<n; j++)  
  38.         {  
  39.             if (sameVal == arr[j])  
  40.             {  
  41.                 *pre = j;  
  42.                 return true;  
  43.             }  
  44.         }  
  45.     }  
  46.     return false;  
  47. }  
  48.  
  49.  
  50.  
  51.  
  52.  
  53. void main(int argc, char *argv[])  
  54. {  
  55.     int prePos = -1, backPos = -1;  
  56.     int myArry[11];  
  57.     myArry[0] = 1;  
  58.     myArry[1] = 3;  
  59.     myArry[2] = 3;  
  60.     myArry[3] = 4;  
  61.     myArry[4] = 5;  
  62.     myArry[5] = 22;  
  63.     myArry[6] = 7;  
  64.     myArry[7] = 13;  
  65.     myArry[8] = 9;  
  66.     myArry[9] = 2;  
  67.     myArry[10] = 12;  
  68.       
  69.       
  70.     if (do_dup_mal(myArry, 11, &prePos, &backPos) )  
  71.         printf("%d\n",myArry[prePos]);  
  72. }  
  73.    

转：http://buptdtt.blog.51cto.com/2369962/749049  

posted on 2014-03-27 19:40 fly 阅读(562) 评论(0)  编辑  收藏 所属分类: 算法

只有注册用户登录后才能发表评论。
网站导航:
 
Copyright ©2025 fly Powered by: 博客园 模板提供：沪江博客