1.暴力统计
直接用map或者set统计数字出现次数即可,注意一旦数字出现两次即可从集合中删除该数字,遍历完剩下的就是要找的数字。
vector<int> FindNumsAppearOnce(vector<int>& array) { // write code here map<int,int> m; for(int i : array) { if(m.count(i)) { m.erase(i); } else{ m[i] = 1; } } vector<int> res; res.push_back((m.begin()->first < m.rbegin()->first) ? (m.begin()->first) : (m.rbegin()->first)) ; res.push_back((m.begin()->first > m.rbegin()->first) ? (m.begin()->first) : (m.rbegin()->first)) ; return res; }
- 异或操作
异或:时间复杂度为O(n),空间复杂度为O(1)
异或概念:对数组中所有数组进行异或(^),即相同为0,不同为1。
设a,b为任意两个数。相同两数异或为0(a^a = 0),0与任何一个数异或为该数本身(a^0=a)。且异或符合交换律(a^b=b^a)。
所以题目中数组所有数字异或后结果为两个不同的数进行异或。(设为a^b)
异或后,从后往前,找到他们二进制中第一个为1的位置,该位置上两个数的二进制不一样否则不可能为1.(设该位置为k)为了划分出来两个数。
那么就可以把原来数组中,这一位是1的分成一组,这一位是0的分成一组。这样就有了两组每一组中会包含一个不同的数和一部分出现两次的数。 然后组内异或就可以了。