数组重复元素求值

题目描述：

数组 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）。

特别注意：

• 如果重复元素不止一个，那么就不能用和差法和异或法，而应该用哈希表

参考资料：
找出数组中唯一重复的数【未完待续】