唯一的重復元素，重復元素

唯一的重復元素，重復元素

問題描述：將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;
}

GCC運行結果：

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

轉載請注明: http://www.cnblogs.com/zpfbuaa