题目
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]
解题
方法一：哈希表(这道题要求空间复杂度为O(1),不符合要求)
class Solution { public: vector<int> singleNumbers(vector<int>& nums) { unordered_map<int,int> map; for(int num:nums){ map[num]++; } vector<int> res; for(pair<int,int> it:map){ if(it.second==1) res.push_back(it.first); } return res; } };
方法二：位运算
使用异或的 方法
但是这个题要找到两个出现一次的数字，因此可以将数组nums划分为2个数组，然后分别对它们做上述操作，就可以得到结果了
由于x和y的异或，相同的位为0，不同的位为1
因此通过m,左移计算，来找到第一个为1(不同)的位
后续遍历num的时候，利用&m，来进行分组，（两个分组，每个分组的数量是未知的，但是其中一个必定包含x，另外一个必定包含y）
for(int num : nums) { if(num & m) x ^= num; // 若 num & m != 0 , 划分至子数组 1 ，执行遍历异或 else y ^= num; // 若 num & m == 0 , 划分至子数组 2 ，执行遍历异或 }
代码
class Solution { public: vector<int> singleNumbers(vector<int>& nums) { int n=0,m=1,x=0,y=0; for(int num:nums){ n^=num; } while((n&m)==0){//一定要加括号（由于优先级） m<<=1; } for(int num:nums){ if(num&m) x^=num; else y^=num; } return {x,y}; } };
