【出自BD面试题】
难度系数：★★★☆☆ 被考察系数：★★★★☆
题目描述：
数组中有N+2个数，其中，N个数出现了偶数次，两个数出现了奇数次（这两个数不相等），请用O（1）的空间复杂度，找出这两个数。注意：不需要知道具体位置，只需要找出这两个数。
分析与解答：
方法一：Hash法
对于本题而言，定义一个HashMap表，把数组元素的值作为key，遍历整个数组，如果key值不存在，则将value设为1，如果key值已经存在，则翻转该值（如果为0，则翻转为1；如果为1，则翻转为0），在完成数组遍历后，Hash表中value为1的就是出现奇数次的数。
例如：给定数组={3，5，6，6，5，7，2，2}；
首先遍历3，HashMap中的元素为：＜3，1＞；
遍历5，HashMap中的元素为：＜3，1＞，＜5，1＞；
遍历6，HashMap中的元素为：＜3，1＞，＜5，1＞，＜6，1＞；
遍历6，HashMap中的元素为：＜3，1＞，＜5，1＞，＜6，0＞；
遍历5，HashMap中的元素为：＜3，1＞，＜5，0＞，＜6，0＞；
遍历7，HashMap中的元素为：＜3，1＞，＜5，0＞，＜6，0＞，＜7，1＞；
遍历2，HashMap中的元素为：＜3，1＞，＜5，0＞，＜6，0＞，＜7，1＞，＜2，1＞；
遍历2，HashMap中的元素为：＜3，1＞，＜5，0＞，＜6，0＞，＜7，1＞，＜2，0＞；
显然，出现1次的数组元素为3和7。(www.xing528.com)
实现代码如下：
程序输出如下：
3
7
性能分析：
这种方法对数组进行了一次遍历，时间复杂度为O（n）。但是申请了额外的存储过程来记录数据出现的情况，因此，空间复杂度为O（n）。
方法二：异或法
根据异或运算的性质不难发现，任何一个数字异或它自己其结果都等于0。所以，对于本题中的数组元素而言，如果从头到尾依次异或每一个元素，那么异或运算的结果自然也就是那个只出现奇数次的数字，因为出现偶数次的数字会通过异或运算全部消掉。
但是通过异或运算，也仅仅只是消除了所有出现偶数次数的数字，最后异或运算的结果肯定是那两个出现了奇数次的数异或运算的结果。假设这两个出现奇数次的数分别为a与b，根据异或运算的性质，将二者异或运算的结果记为c，由于a与b不相等，所以，c的值自然也不会为0，此时只需知道c对应的二进制数中某一个位为1的位数N，例如，十进制数44可以由二进制数00101100表示，此时可取N=2或者3，或者5，然后将c与数组中第N位为1的数进行异或，异或结果就是a和b中的一个，然后用c异或其中一个数，就可以求出另外一个数了。
通过上述方法为什么就能得到问题的解呢？其实很简单，因为c中第N位为1表示a或b中有一个数的第N位也为1，假设该数为a，那么，当将c与数组中第N位为1的数进行异或时，也就是将x与a外加上其他第N位为1的出现过偶数次的数进行异或，化简即为x与a异或，结果即为b。
示例代码如下：
程序的运行结果如下：
3 7
算法性能分析：
这种方法首先对数组进行了一次遍历，其时间复杂度为O（N），接着找result对应二进制数中位值为1的位数，时间复杂度为O（1），接着又遍历了一次数组，时间复杂度为O（N），因此，这种方法整体的时间复杂度为O（N）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
