<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        




    
	
		


    隨筆 - 100 
文章 - 50 
trackbacks - 0


     
	

    

    
	
		
    
			
    
	
    
		
    <2014年3月>
    
	
    日一二三四五六
    2324252627281
    2345678
    9101112131415
    16171819202122
    23242526272829
    303112345
    

    

    
			
			

    常用鏈接
    


    留言簿(3)
    




		
    隨筆分類
    
		
				
			
	
		
    隨筆檔案
    
		
				
			
	
		
    文章分類
    
		
				
			
	
		
    文章檔案
    
		
				
			
	
		
    收藏夾
    
		
				
			
	
		
    我收藏的一些文章!
    
		
				
			
	




    搜索
    

      
	
    • 
		
    •  
	
      • 

    


    最新評論
	
    

    
	
			
		

    


    閱讀排行榜
    



    評論排行榜
    


    		
	

    

    
	
					


    
	
	
    題目：
    

    數(shù)組a[N]，1至N-1這N-1個數(shù)存放在a[N]中，其中某個數(shù)重復(fù)一次。寫一個函數(shù)，找出被重復(fù)的數(shù)字。
    

    方法一：異或法。
    

    數(shù)組a[N]中的N個數(shù)異或結(jié)果與1至N-1異或的結(jié)果再做異或，得到的值即為所求。
    

    • 設(shè)重復(fù)數(shù)為A，其余N-2個數(shù)異或結(jié)果為B。 
    • N個數(shù)異或結(jié)果為A^A^B 
    • 1至N-1異或結(jié)果為A^B 
    • 由于異或滿足交換律和結(jié)合律，且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. }   
    

     方法二：數(shù)學(xué)法。
    

    對數(shù)組的所有項求和，減去1至N-1的和，即為所求數(shù)。
    

     
    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. }   
    

    對于求和，可以直接根據(jù)公式定義一個宏。#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. }   
    

     方法三：標(biāo)志數(shù)組法
    

    申請一個長度為n-1且均為'0'組成的字符串。然后從頭遍歷a[n]數(shù)組，取每個數(shù)組元素a[i]的值，將其對應(yīng)的字符串中的相應(yīng)位置置1，如果已經(jīng)置過1的話，那么該數(shù)就是重復(fù)的數(shù)。就是用位圖來實(shí)現(xiàn)的。 如果考慮空間復(fù)雜度的話，其空間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;          // 置出現(xiàn)標(biāo)志  
    21.           
    22.         else      
    23.         {   
    24.             printf("%d\n",arr[i]);  
    25.             return ; //返回已經(jīng)出現(xiàn)的值  
    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。原數(shù)組a[i]最大是N-1，若a[i]=K在某處出現(xiàn)后，將a[K]加一次N，做標(biāo)記，當(dāng)某處a[i]=K再次成立時，查看a[K]即可知道K已經(jīng)出現(xiàn)過。該方法不用另外開辟O(N)的內(nèi)存空間，但是在查重之后要將數(shù)組進(jìn)行恢復(fù)。
    

     
    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;            // 該值重復(fù)了，因?yàn)樵?jīng)加過一次了        
    13.         else              
    14.             temp=arr[i];          
    15.                   
    16.         if(arr[temp]<NUM)         
    17.         {         
    18.             arr[temp]+=NUM; //做上標(biāo)記            
    19.         }  
    20.           
    21.         else              
    22.         {             
    23.             printf("有重復(fù) %d\n",temp);              
    24.             return;           
    25.         }         
    26.     }  
    27.               
    28.     printf("無重復(fù)");  
    29.     return ;   
    30. }    
    31. void clear(int *data,int num)//清理數(shù)據(jù)  
    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. }    
    

     方法五：符號標(biāo)志法
    

    上個方法出現(xiàn)后是加N，也可以出現(xiàn)后加個負(fù)號，就是符號標(biāo)志法。
    

     
    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];  // 該值重復(fù)了，因?yàn)樵?jīng)加過一次了     
    14.         else                           
    15.             temp=arr[i];                
    16.         if(arr[temp]>0)             
    17.         {                    
    18.             arr[temp]=0-arr[temp]; //做上標(biāo)記        
    19.         }                
    20.         else              
    21.         {               
    22.             printf("有重復(fù) %d\n",temp);      
    23.             return;               
    24.         }            
    25.     }                
    26.     printf("無重復(fù)");    
    27.     return ;    
    28.  }     
    29.  void clear(int *data,int num)//清理數(shù)據(jù)  
    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.  }      
    

    以上的方法對數(shù)組元素的值的范圍是有限制的，如果數(shù)組元素的值不是在1至N-1范圍時，可以先求出數(shù)組元素的最大值。
    

     
    

    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];//找出數(shù)組中的最大數(shù)  
    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'; // 置出現(xiàn)標(biāo)志  
    27.         else 
    28.         {  
    29.             sameVal = arr[i]; //返回已經(jīng)出現(xiàn)的值  
    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.    
    

    轉(zhuǎn)：http://buptdtt.blog.51cto.com/2369962/749049  
    
	
    posted on 2014-03-27 19:40 fly 閱讀(535) 評論(0)  編輯  收藏  所屬分類: 算法 
    

    







    
	    
    




    








    

				
	



    



    







    
        
	



主站蜘蛛池模板：
日本黄色免费观看|
国产偷国产偷亚洲清高APP|
又色又污又黄无遮挡的免费视|
精品成人免费自拍视频|
久久综合亚洲色hezyo|
亚洲伊人色一综合网|
亚洲av无码成h人动漫无遮挡|
亚洲天堂中文字幕在线|
日韩成人免费视频播放|
久久经典免费视频|
50岁老女人的毛片免费观看|
国内精品99亚洲免费高清|
阿v视频免费在线观看|
亚洲精品乱码久久久久久V|
亚洲成a人片毛片在线|
亚洲国产天堂在线观看|
国产专区一va亚洲v天堂|
国产免费无遮挡精品视频|
成人免费午间影院在线观看|
av无码国产在线看免费网站|
老汉精品免费AV在线播放|
免费观看男人吊女人视频|
国产免费一级高清淫曰本片|
日亚毛片免费乱码不卡一区
|
毛片在线播放免费观看|
一区二区三区在线观看免费
|
亚洲AV无码一区二三区
|
亚洲av午夜电影在线观看|
亚洲欧洲日产国码久在线|
亚洲免费一级视频|
亚洲制服丝袜中文字幕|
亚洲人成在线中文字幕|
亚洲人成免费电影|
亚洲精品一二三区|
亚洲精品无码中文久久字幕|
亚洲精品无码成人|
色五月五月丁香亚洲综合网|
边摸边脱吃奶边高潮视频免费|
美女视频黄a视频全免费网站一区|
免费手机在线看片|
一级毛片在线免费播放|