在網上看到一個這樣的題：
一個數組中含有1001個元素，存放了1,2,3...1000和一個重復的數。只有唯一一個數是重復的，其它均只出現一次。要求設計一個算法找出這個重復的數，要求：每個數組元素只能訪問一次，不用輔助存儲空間。
解法一：
最簡單的方法是，先求出1...1000的和（用公式：n(n+1)/2）sum1，然後求出arr[0]...arr[1000]的和sum2，（sum2-sum1）便是要求的結果。該方法只用遍歷數組一次即可。
解法二：
可以用bit-map，先將bit-map所有位標記為1，然後將數組循環一遍，依次將每個元素讀入bit-map，如果對應位為0，則標記為1，如果對應位為1，則該數便是要求的結果。該方法也只用遍歷數組一次。但是，題目中要求不用輔助存儲空間，而這裡使用了bit-map為輔助存儲空間，顯然不符合要求，不過該方法的思想是不錯的。而且當該數組的范圍非常大時，用解法一進行求和時可能會溢出，而該解法卻是不錯的選擇。
解法三：
本文其實想好好說說解法三，該方法是在網上看到的，覺得很巧妙也挺有意思，在這裡跟大家分享一下。主要利用了公式：a ^ b ^ a = b。代碼如下：
[cpp]
#include <iostream>
using namespace std;
int findRepeat(const int arr[], const size_t len)
{
int res = arr[0];
for (int i = 1; i < len; i++)
{
res ^= i;
res ^= arr[i];
}
return res;
}
int main()
{
int arr[6] = {1, 2, 3, 4, 5, 3};
int res = findRepeat(arr, 6);
cout << "The repeat number is : " << res << endl;
return 0;
}
#include <iostream>
using namespace std;
int findRepeat(const int arr[], const size_t len)
{
int res = arr[0];
for (int i = 1; i < len; i++)
{
res ^= i;
res ^= arr[i];
}
return res;
}
int main()
{
int arr[6] = {1, 2, 3, 4, 5, 3};
int res = findRepeat(arr, 6);
cout << "The repeat number is : " << res << endl;
return 0;
}函數findRepeat中的res為異或的中間結果，res ^= i是異或1...1000每個數，res ^= arr[i]是異或arr[0]...arr[1000]每個元素，執行完for循環後，除了重復的那個數異或了3次外，其他所有的數異或了2次，因此res就是重復的那個數。例如，對於上面main函數中的測試數組，res的求值過程為：res = 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4 ^ 4 ^ 5 ^ 5 ^ 3，結果為3。該解法也只用遍歷數組一次，而且對於數組范圍非常大時，不會出現溢出的情況。
當然還有很多其他的方法。
