唯一的重複元素

找到唯一的重複出現數字 （使用位運算）

問題描述：将1~1000放在含有1001個元素的數組中，隻有唯一的一個元素重複，其他均出現一次。請設計一個算法，将這個唯一重複的元素找出來，要求每個數組元素隻能通路一次，且不能使用輔助存儲空間。

　解決方法1：根據題目描述隻要将數組中的1001個數求和得到sum0，然後減去1到1000的和sum1就可以得到這個唯一的重複數字。

　參考代碼：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    srand(time(NULL));
    int pos = rand() % 1002 ;
    int num = rand() % 1002 ;
    cout<<"随機産生的數字為: "<<num<<endl ;
    int sum0 = 0 ;
    int sum1 = 0 ;
    for( int i = 1 ; i <= 1000 ; i ++ )
    {
        if( i == pos)
        {
            sum0 += num ;
            sum0 += pos ;
        }
        else
        {
            sum0 += i ;
        }
        sum1 += i ;
    }
    cout<<"唯一重複的數字為: "<<sum0 - sum1<<endl;
}      

GCC運作結果：

解題方法2：

該方法根據異或 a^b^a = b; 那麼我們可以讓出現兩次的進行多進行一次異或，出現一次的多進行一次異或，也就是a^b^a^a^b =a;  

(因為a^b^a=b  b^a^b=a)

參考代碼：

#include <bits/stdc++.h>

using namespace std;
int findRepeat(const int a[])
{
    int temp = a[0] ;
    for( int i = 1 ; i <1001 ; i ++ )
    {
        temp ^= i;
        temp ^= a[i];
    }
    return temp;
}
int main()
{
    srand(time(NULL)) ;
    int num = rand() % 1002 ;
    cout<<"随機産生的數字為: "<<num<<endl ;
    int a[1001] ;
    memset( a , 0 , sizeof( a ) ) ;
    a[0] = num ;
    for( int i = 1 ; i < 1001 ; i ++ )
    {
        a[i] = i ;
    }
    cout<<"唯一重複的數字為: "<<findRepeat(a)<<endl;
}      

希望能夠得到其他的解決方法。

轉載請注明: