数组重复元素求值
题目描述：
数组 a[N] 中存放了 1 至 N - 1 个数，其中某个数重复了一次。求找出重复元素，时间复杂度必须为 O（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 <iostream>
using namespace std;
void 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;
}
cout << result << endl;
}
int main()
{
int a[] = {3, 1, 2, 3, 4};
FindDup(a, 5);
return 0;
}
分析：运算次数是 2 * N - 1。最好最坏时间复杂度都是 O（n），空间复杂度是 O（1）。
解法二：和差法
对数组的所有项求和，减去 1 至 N - 1 的和，即为所求数。
源代码如下：
#include <iostream>
using namespace std;
void FindDup(int* a, int N)
{
int result = 0;
for (int i = 0; i < N; i++)
{
result += a[i];
}
result -= N * (N - 1) / 2;
cout << result << endl;
}
int main()
{
int a[] = {3, 1, 2, 5, 4, 2, 6, 7};
FindDup(a, 8);
return 0;
}
分析：运算次数是 N + 1 。最好最坏时间复杂度都为 O（n），空间复杂度为 O（1）。
解法三：哈希表
申请一个长度为 N - 1 且均为 '0' 组成的辅助数组 b[N] 。然后从头遍历 a[N] 数组，取每个数组元素 a[i] 的值，将其对应的 b[a[i]] 置 1 。如果该元素已经置过 1 的话，那么该元素就是重复的元素。
源代码如下：
#include <iostream>
#include <cstring>
using namespace std;
void FindDup(int* a, int N)
{
int b[N];
memset(b, 0, sizeof(int) * N);
for (int i = 0; i < N; i++)
{
if (b[a[i]] == 0)
b[a[i]] = 1;
else
{
cout << a[i] << endl;
return;
}
}
}
int main()
{
int a[] = {3, 2, 1, 5, 4, 8, 6, 7, 9, 1};
FindDup(a, 10);
return 0;
}
分析：最好运算次数是 2 ，最坏运算次数是 N ，所以最好时间复杂度是 O（1） ，最坏时间复杂度是 O（n） 。空间复杂度是 O（n）。
特别注意：
- 如果重复元素不止一个，那么就不能用和差法和异或法，而应该用哈希表
参考资料：
找出数组中唯一重复的数【未完待续】
