數(shù)組重復(fù)元素求值
題目描述：
數(shù)組 a[N] 中存放了 1 至 N - 1 個(gè)數(shù)，其中某個(gè)數(shù)重復(fù)了一次。求找出重復(fù)元素，時(shí)間復(fù)雜度必須為 O（N）。
分析和解法：
解法一：異或法
數(shù)組 a[N] 中的 N 個(gè)數(shù)異或結(jié)果與 1 至 N - 1 異或的結(jié)果再做異或，得到的值即為所求。
- 設(shè)重復(fù)數(shù)為 A ，其余 N - 2 個(gè)數(shù)異或結(jié)果為 B
- N 個(gè)數(shù)異或結(jié)果為 A ^ A ^ B
- 1 至 N - 1 異或結(jié)果為 A ^ B
- 由于異或滿足交換律和結(jié)合律，且 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;
}
分析：運(yùn)算次數(shù)是 2 * N - 1。最好最壞時(shí)間復(fù)雜度都是 O（n），空間復(fù)雜度是 O（1）。
解法二：和差法
對(duì)數(shù)組的所有項(xiàng)求和，減去 1 至 N - 1 的和，即為所求數(shù)。
源代碼如下：
#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;
}
分析：運(yùn)算次數(shù)是 N + 1 。最好最壞時(shí)間復(fù)雜度都為 O（n），空間復(fù)雜度為 O（1）。
解法三：哈希表
申請(qǐng)一個(gè)長度為 N - 1 且均為 '0' 組成的輔助數(shù)組 b[N] 。然后從頭遍歷 a[N] 數(shù)組，取每個(gè)數(shù)組元素 a[i] 的值，將其對(duì)應(yīng)的 b[a[i]] 置 1 。如果該元素已經(jīng)置過 1 的話，那么該元素就是重復(fù)的元素。
源代碼如下：
#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;
}
分析：最好運(yùn)算次數(shù)是 2 ，最壞運(yùn)算次數(shù)是 N ，所以最好時(shí)間復(fù)雜度是 O（1） ，最壞時(shí)間復(fù)雜度是 O（n） ?？臻g復(fù)雜度是 O（n）。
特別注意：
- 如果重復(fù)元素不止一個(gè)，那么就不能用和差法和異或法，而應(yīng)該用哈希表
