C ++程序查找数组中奇数次出现的整数

给定一个整数数组，其中一个数字（整数）必须重复奇数次，我们必须找到一个整数。

示例

    Input:
    Array elements are: [1, 4, 6, 1, 9, 6, 4]
    
    Output:
    In this array output will be 9

有两种找到它的方法：

1）天真的方法

在这种方法中，我们将不得不遍历数组多次，并计算该数组中每个整数的出现次数。这将给我们O（n ²）时间复杂性，因为我们必须遍历所有n个元素的每个数字。

2）X-OR方法

此方法是最佳方法，因为它具有O(n)时间复杂度，因为仅遍历数组一次即可找到解决方案。此方法使用位操作。

    A	B	Y
    0	0	0
    0	1	1
    1	0	1
    1	1	0

当给定两个相同的数字作为输入时，输出为零，而给定数字（例如x）和零作为输入时，它将给输出相同的数字(x)。

现在让我们举一个例子，使它更容易理解。

    [1, 4, 6, 1, 9, 6, 4]
    
    At first result=0
    Then,

    0^1     = 1     result  = 1
    1^4     = 5     result  = 5
    5^6     = 3     result  = 3
    3^1     = 2     result  = 2
    2^9     = 11    result  = 11
    11^6    = 13    result  = 13
    13^4    = 9     result  = 9

C ++代码：

#include <iostream>
#include <vector>

using namespace std;

//查找奇数整数的功能
int oddInteger(vector <int> a) 
{
    int result=0;
    for(unsigned int i=0;i<a.size();i++)
    {
        result=result^a[i];        
    }
    return result;    
}

//测试代码的主要功能
int main() {
    int n;
    //输入元素总数
    cin >> n;
    vector<int> a(n);
    
    //读取n个数字
    for(int i=0;i<n;i++)
    {
       cin>>a[i];
    }
    
    //查找并打印结果
    int result = oddInteger(a);
    cout << result << endl;
    
    return 0;
}

输出结果

9