《剑指offer》题目40：数组中只出现一次的数字

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求的时间复杂度是O(n)

因为OJ牛客网，没有要求时间复杂度，开始的时候采用暴力解法时间复杂度是$O（n^2）$，书中要求复杂度是 $O（n）$

分析：题目可以抽象成这样，有两个数字出现了奇数次，其他数字出现了偶数次。我们可以想到用异或运算，对偶数次的数字异或后得0，奇数次的数字异或后得1。基于这样的事实：两个不同的数字必然至少有一位不同，进行xor运算后必然有一位为1。 解法如下：

数组里的数字依次进行xor。找出第一个1所在的索引。将数组里的数字按照索引位是否为1，分为两组。两个组里数字分别xor，最后两组里分别剩下的数字即为所求

---

代码如下：

#include "stdafx.h" #include"iostream" #include"vector" using namespace std; void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) { if (data.size() < 2) return; int xorRes= 0; for (int i = 0; i < data.size(); i++) { xorRes ^= data[i]; } int count = 0; while (!(xorRes>>1)&1) { count++; } for (int i = 0; i < data.size(); i++) { if ((data[i] >> count) & 1) { *num1 ^= data[i]; } else { *num2 ^= data[i]; } } } int main() { vector<int> data = { 0,0,1,2,3,3,4,4 }; int num1=0; int num2=0; FindNumsAppearOnce(data, &num1,& num2); system("pause"); return 0; }