java fans

隨筆 - 100 文章 - 50 trackbacks - 0

<

2014年3月

>

日

一

二

三

四

五

六

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

常用鏈接

留言簿(3)

隨筆分類

隨筆檔案

文章分類

文章檔案

收藏夾

我收藏的一些文章!

java編程
other
覺得他寫的一些文章不錯，就鏈接了，：）
好友博客
流星絮語

搜索

閱讀排行榜

評論排行榜

找出數組中唯一重復的數

題目：

數組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

代碼：

#include <stdio.h>  
#include <stdlib.h>  
#include <math.h>  
#include<time.h>  
void xor_findDup(int * a,int N)    
{    
    int i;    
    int result=0;    
    for(i=0;i<N;i++)    
    {    
        result ^= a[i];    
    }    
      
    for (i=1;i<N;i++)     
    {    
        result ^= i;    
    }    
      
    printf("%d\n",result);    
      
}    
 
 
 
int main(int argc, char* argv[])    
{    
    int a[] = {1,2,1,3,4};    
    xor_findDup(a,5);    
    return 0;    
}

方法二：數學法。

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

#include <stdio.h>  
#include <stdlib.h>  
#include <math.h>  
#include<time.h>  
void xor_findDup(int * a,int N)    
{    
    int tmp1 = 0;  
      
    int tmp2 = 0;  
      
    for (int i=0; i<N-1; ++i)  
          
    {  
          
        tmp1+=(i+1);  
          
        tmp2+=a[i];  
          
    }  
    tmp2+=a[N-1];  
    int result=tmp2-tmp1;     
    printf("%d\n",result);    
      
}    
 
 
 
int main(int argc, char* argv[])    
{    
    int a[] = {1,2,4,3,4};    
    xor_findDup(a,5);    
    return 0;    
}

對于求和，可以直接根據公式定義一個宏。#define sum(x) (x*(x+1)/2)

#include <stdio.h>  
#include <stdlib.h>  
#include <math.h>  
#include<time.h>  
#define sum(x)  (x*(x+1)/2)   
void xor_findDup(int * a,int N)    
{    
    int tmp1 = sum((N-1));//注意N-1要加括號     
    int tmp2 = 0;  
      
    for (int i=0; i<N; ++i)       
    {             
        tmp2+=a[i];   
    }  
    int result=tmp2-tmp1;     
    printf("%d\n",result);        
}    
 
int main(int argc, char* argv[])    
{    
    int a[] = {1,2,4,2,3};    
    xor_findDup(a,5);    
    return 0;    
}

方法三：標志數組法

申請一個長度為n-1且均為'0'組成的字符串。然后從頭遍歷a[n]數組，取每個數組元素a[i]的值，將其對應的字符串中的相應位置置1，如果已經置過1的話，那么該數就是重復的數。就是用位圖來實現的。如果考慮空間復雜度的話，其空間O（N）

#include <stdio.h>  
#include <stdlib.h>  
#include <math.h>  
#include<time.h>  
#define sum(x)  (x*(x+1)/2)   
void xor_findDup(int * arr,int NUM)    
{    
    int *arrayflag = (int *)malloc(NUM*sizeof(int));      
    int i=1;  
      
    while(i<NUM)  
    {  
        arrayflag[i] = false;  
        i++;  
    }     
      
    for( i=0; i<NUM; i++)         
    {         
        if(arrayflag[arr[i]] == false)            
            arrayflag[arr[i]] = true;          // 置出現標志  
          
        else      
        {   
            printf("%d\n",arr[i]);  
            return ; //返回已經出現的值  
        }  
          
     }    
}    
 
int main(int argc, char* argv[])    
{    
    int a[] = {1,3,2,4,3};    
    xor_findDup(a,5);    
    return 0;    
}

方法四：固定偏移量法

a[N]，里面是1至N-1。原數組a[i]最大是N-1，若a[i]=K在某處出現后，將a[K]加一次N，做標記，當某處a[i]=K再次成立時，查看a[K]即可知道K已經出現過。該方法不用另外開辟O(N)的內存空間，但是在查重之后要將數組進行恢復。

#include <stdio.h>  
#include <stdlib.h>  
#include <math.h>  
#include<time.h>  
void xor_findDup(int * arr,int NUM)    
{    
    int temp=0;       
    for(int i=0; i<NUM; i++)          
    {  
          
        if(arr[i]>=NUM)           
            temp=arr[i]-NUM;            // 該值重復了，因為曾經加過一次了        
        else              
            temp=arr[i];          
                  
        if(arr[temp]<NUM)         
        {         
            arr[temp]+=NUM; //做上標記            
        }  
          
        else              
        {             
            printf("有重復 %d\n",temp);              
            return;           
        }         
    }  
              
    printf("無重復");  
    return ;   
}    
void clear(int *data,int num)//清理數據  
{  
    for(int i=0;i<num;i++)  
    {  
        if(data[i]>num)  
            data[i]-=num;  
    }  
 
}  
int main(int argc, char* argv[])    
{    
    int a[] = {2,4,3,4,1};    
    xor_findDup(a,5);    
    clear(a,5);  
    return 0;    
}

方法五：符號標志法

上個方法出現后是加N，也可以出現后加個負號，就是符號標志法。

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include<time.h>  
 
void xor_findDup(int * arr,int NUM)    
{         
    int temp=0;          
    for(int i=0; i<NUM; i++)        
    {                    
        if(arr[i]<0)     
            temp=0-arr[i];  // 該值重復了，因為曾經加過一次了     
        else                           
            temp=arr[i];                
        if(arr[temp]>0)             
        {                    
            arr[temp]=0-arr[temp]; //做上標記        
        }                
        else              
        {               
            printf("有重復 %d\n",temp);      
            return;               
        }            
    }                
    printf("無重復");    
    return ;    
 }     
 void clear(int *data,int num)//清理數據  
 {     
     for(int i=0;i<num;i++)     
     {        
         if(data[i]<0)           
             data[i]=0-data[i];     
   }     
}    
 int main(int argc, char* argv[])    
 {        
     int a[] = {3,2,1,4,1};       
     xor_findDup(a,5);     
     clear(a,5);      
     return 0;    
 }

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include<time.h>
int do_dup_mal(int arr[], int n, int *pre, int *back)
{
int MAX = -1;
int i = 0;
int sameVal = -1;
*pre = *back = -1;
for (int j=0; j<n; j++)
{
if (arr[j] > MAX) MAX = arr[j];//找出數組中的最大數
}
char *arrayflag = new char[MAX+1] ;
if (NULL == arrayflag)
return -1;
memset(arrayflag, 0, MAX+1 ); // '\0' == 0
for(i=0; i<n; i++)
{
if(arrayflag[arr[i]] == '\0')
arrayflag[arr[i]] = '\1'; // 置出現標志
else
{
sameVal = arr[i]; //返回已經出現的值
*back = i;
break;
}
}
delete[] arrayflag;
if (i < n)
{
for (int j=0; j<n; j++)
{
if (sameVal == arr[j])
{
*pre = j;
return true;
}
}
}
return false;
}
void main(int argc, char *argv[])
{
int prePos = -1, backPos = -1;
int myArry[11];
myArry[0] = 1;
myArry[1] = 3;
myArry[2] = 3;
myArry[3] = 4;
myArry[4] = 5;
myArry[5] = 22;
myArry[6] = 7;
myArry[7] = 13;
myArry[8] = 9;
myArry[9] = 2;
myArry[10] = 12;
if (do_dup_mal(myArry, 11, &prePos, &backPos) )
printf("%d\n",myArry[prePos]);
}

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

posted on 2014-03-27 19:40 fly 閱讀(538) 評論(0) 編輯收藏所屬分類: 算法

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 找出數組中唯一重復的數快速排序（Quicksort）的Javascript實現（轉） java實現快速排序(轉) 字符串匹配算法總結（轉） Boyer-Moore 經典單模式匹配算法（轉）