题. 数组中只出现一次的两个数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。
你可以假设这两个数字一定存在。
数据范围
数组长度 [1,1000]。
样例
输入：[1,2,3,3,4,4]
输出：[1,2]【题解】--- 异或
任何一个数字异或他自己都等于0，从头到尾异或所有数字之后，出现两次的数字相互异或会变成0，所以最终的结果会是x异或y，也即两个仅出现一次的数字的异或。
x^y这个异或结果一定不为0，因为x不等于y，所以肯定至少有一位为1。我们找到这个结果中第一个为1的位，在这个位上x和y的二进制表示肯定相反。
所以我们可以对于原先的数组，根据该位是否为1，将其划分成两个数组，这样两个数组中就分别存在一个仅出现一次的数字。我们再分别对两个数组进行异或运算，最后分别剩下的结果，就是x和y
异或得到 x^y；
- 取 x与y中第k位为1的数；
- 将数分为两个集合，第k位为1的集合和第k位不是1的集合；
- 其中x y分别在这两个集合，且相同的元素是在同一个集合里面；
- 最终将其转化成了求重复数字中的单个数值的问题。
复杂度分析：
时间复杂度因为只遍历结点一次，所以最坏情形为O(n)C++代码实现：
class Solution {
public:
vector<int> findNumsAppearOnce(vector<int>& nums) {
int sum = 0;
for(auto x : nums) sum ^=x;
int k = 0;
while(!(sum>>k & 1))k++;
int first = 0;
for(auto x: nums)
if(x>>k&1)
first ^= x;
return vector<int>{first,sum^first};
}
};
