algorithm - 查找数组中出现偶数次的三个数字

Question

在一个数组中，除三个数字外，所有数字都出现奇数次。如何找到数组中出现偶数次的所有三个数字？

我可以得到所有三个偶数的异或值。如何从该异或值中获取三个数字？到目前为止我的方法:

#include <iostream>
#include <set>
using namespace std;

int main() {
    // Find the 3 numbers occuring even times in an array
    int arr[] = {1,6,2,88,34,4,98,25,61,7,2,78,2,78,8,25,9,34,56,331};
    int a = arr[0];

    for (int i=1;i<20;i++)
         a ^= arr[i];

    set<int> myset;
    myset.insert(arr,arr+20);
    set<int>::iterator it;
    for (it=myset.begin(); it!=myset.end(); ++it)
        a ^= *it;

    cout<<a<<endl; // a stores xor of the three numbers occuring even number of times, i.e., (25^78^34)=117
    return 0;
}

注意:不应使用哈希表和排序。解决方案应该在 O(n) 时间内。

Answer 1

你的问题的解决方案是

`
#include <iostream>
#include <set>
using namespace std;

int main() {
    // Find the 3 numbers occuring even times in an array
    int arr[] = {1,6,2,88,34,4,98,25,61,7,2,78,2,78,8,25,9,34,56,331};
    set<int> myset;
set<int> myset_final;


    for (int i=1;i<20;i++)
    {
    if(myset.exists(a[i]))
        myset.remove(a[i]);
    else myset.insert(a[i]);
    }
for(int i=0;i<i<20;i++)
{
    if(!myset.exists(a[i]))
        myset_final.insert(a[i]);
}
    //Now the myset_final contains the numbers that are occured even number of times.
return 0;
}
`

这是我认为的最佳解决方案，但不是 O(n) 而是 O(nlog(n))。