一个数组中有三个数字a、b、c只出现一次，其他数字都出现了两次。请找出三个只出现一次的数字。
本文参考：
题目：一个数组里，除了三个数是唯一出现的，其余的都出现偶数个，找出这三个数中的任一个。
比如数组元素为【1, 2,4,5,6,4,2】，只有1,5,6这三个数字是唯一出现的，我们只需要输出1,5,6中的一个就行。
解题思路：
在这道题中，如果我们能够找出一个只出现一次的数字，剩下两个只出现一次的数字就很容易找出来了。这个数组元素个数一定为奇数，而且那要求的三个数一定不可能每一bit位都相同，所以我们可以根据第一个不同的bit位，可以把那三个数字分出来，而且可以推出三个数肯定可以分到两组不同的数组里面去，基于这样的思路就可以找出这三个不同的数字。
下面是找到数组中一个不同的数字：
//返回数组中一个不重复的数
int FindSingleNumber(int arr[],int
invaluedInput =
if(NULL == arr || len&3)
invaluedInput =
int tmpA = 0;
int tmpB = 0;
int countA = 0;
int countB = 0;
int i = 0;
int j = 0;
for(i=0; i&32; i++)
tmpA = tmpB = countA = countB = 0;
//根据第i位的不同，将数组中的元素分为2部分，tmpA、tmpB分别异或两部分元素
for(j=0; j& j++)
if(IsNumOf1(arr[j],i))
tmpA ^= arr[j];
tmpB ^= arr[j];
//如果countA为奇数，那么tmpA异或的那部分元素或者包含三个不重复元素中的一个，或者包含全部三个不重复的元素
if(countA & 0x1)
if(0 == tmpB)//如果tmpB为0，那么可得tmpA异或的那部分数据中包含全部的三个不重复元素，所有三个不重复元素的当前的第i位都相同，不足以区分。
//printf(&%d\n&,tmpA);
return tmpA;//因为tmpB不为0，countA为奇数，那么countB就为偶数，并且tmpB异或的那部分数据中包含2个不重复元素，此时tmpA异或的那部分数据就只包含一个不重复的数据。
else //否则countA为偶数，那么countB为奇数
if(0 == tmpA)//同理：如果tmpA为0，那么可得tmpB异或的那部分数据中包含全部的三个不重复元素，所有三个不重复元素的当前的第i位都相同，不足以区分。
// printf(&%d\n&,tmpB);
return tmpB;//否则tmpA那部分数据集合中包含2个不重复的元素，tmpB的那部分数据集合中包含一个不重复的元素，异或结果中相同的数抵消，结果就是tmpB，返回
}总结下上面的思路就是：
1、原数组的个数一定是奇数
2、按照某一位是1还是0分为两个数组：分成两个数组一个是奇数个元素，一个是偶数个元素 ，相同的数字一定会被分到同一组里，&分出来的两个数组各自异或的结果，奇数个数的数组肯定不为0（包含1个或3个不重复的元素）。偶数个数的数组可能为0（不包含不重复的元素），可能不为0（包含2个不重复的元素）。偶数个数的数组异或结果为0，表示三个不重复的数都被分到同一组中了，包含此部分数的数组有奇数个元素。另一偶数部分的数组中不包含不重复的元素。偶数个数的数组异或结果不为0，表示偶数个数的数组里包含2个出现一次的数，那么奇数个数的数组中包含一个不重复的数，由于相同元素异或为0，相抵消，奇数个数的数组所有数的异或结果就为那个不重复的数。
3、找到一个不重复的元素后就可以很方便的找到剩下的两个不重复的元素。
代码如下：
//找到两个只出现一次的数，通过引用tmpA,tmpB返回。，singleNum为FindSingleNumber函数返回的数组中的一个不重复的元素。
void FindOnceNum(int arr[],int len,int& tmpA,int& tmpB,int singleNum)
invaluedInput =
if(NULL == arr || len&2)
invaluedInput =
int i = 0;
int result = 0;
int tmp = 0;
for(i=0; i& i++)
result ^= arr[i];
/*result与所有数组元素都异或过后，还应该与singleNum异或来抵消FindSingleNumber函数返回的数组中的那个不重复的元素，这样数组就只剩下2个不重复的元素*/
result ^= singleN
//找到第一个不为0的位
tmp = TheFirst1OfNum(result);
//result为0则数组中不存在不重复的元素，输入有误，返回。
if(tmp == 0)
invaluedInput =
//根据result的第一个不为1的位将数组元素分为两部分。
for(i=0; i& i++)
if(arr[i] & tmp)
tmpA ^= arr[i];
tmpB ^= arr[i];
//记得还要将singleNum加进来，才能保证数组中只有2个不同的元素。
if(singleNum & tmp)
tmpA ^= singleN
tmpB ^= singleN
上面函数完成寻找数组中只有两个不重复元素的功能，通过引用返回。
寻找数组中只要两个不重复元素的方法为：任何数字异或它自己结果都为0.也就是说如果数组中只有1个不重复的元素，那么从头到尾依次异或，最终结果刚好是那个只出现一次的数字，那些成对出现两次的数字全部在异或中抵消了。
那么对于寻找数组中两个不重复的元素：我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现依次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消了。由于这两个数字肯定不一样，那么异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1，我们在结果数字钟找到第一个为1的位的位置，记为n位。现在我们一第n为是不是1的位标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0.由于我们分组的标准时数字中的某一位是1还是0，那么出现了两次的数字肯定被分配到同意个子数组。因为两个相同的数字的任意一位都是相同的，我们不可能把两个相同的数字分配到两个子数组中区，于是我们已经把原数组分成两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。我们已经知道如何在数组中找出唯一一个只出现一次数组，因此到此为止所有的问题都已经解决了。
举个例子，假设输入数组{2,4,3,6,3,2,5,5}。当我们依次对数组中的每一个数字做异或运算之后，得到结果用二进制表示是0010.异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1分为两个数组。第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1，而第二个子数组{4,5,5}中所有数字的倒数第二位都是0.接下来只要分别对这两个子数组求异或，就能找出第一个子数组中只出现依次的数字是6，而第二个子数组中只出现一次的数字是4.
解决本题的完整代码如下：
#include &iostream&
#include &stdio.h&
//错误标记
bool invaluedInput =
//检查num的第n位是否为1
bool IsNumOf1(int num,int n)
if(num & (1&&n))
//返回数组中一个不重复的数
int FindSingleNumber(int arr[],int
invaluedInput =
if(NULL == arr || len&3)
invaluedInput =
int tmpA = 0;
int tmpB = 0;
int countA = 0;
int countB = 0;
int i = 0;
int j = 0;
for(i=0; i&32; i++)
tmpA = tmpB = countA = countB = 0;
//根据第i位的不同，将数组中的元素分为2部分，tmpA、tmpB分别异或两部分元素
for(j=0; j& j++)
if(IsNumOf1(arr[j],i))
tmpA ^= arr[j];
tmpB ^= arr[j];
//如果countA为奇数，那么tmpA异或的那部分元素或者包含三个不重复元素中的一个，或者包含全部三个不重复的元素
if(countA & 0x1)
if(0 == tmpB)//如果tmpB为0，那么可得tmpA异或的那部分数据中包含全部的三个不重复元素，所有三个不重复元素的当前的第i位都相同，不足以区分。
//printf(&%d\n&,tmpA);
return tmpA;//因为tmpB不为0，countA为奇数，那么countB就为偶数，并且tmpB异或的那部分数据中包含2个不重复元素，此时tmpA异或的那部分数据就只包含一个不重复的数据。
else //否则countA为偶数，那么countB为奇数
if(0 == tmpA)//同理：如果tmpA为0，那么可得tmpB异或的那部分数据中包含全部的三个不重复元素，所有三个不重复元素的当前的第i位都相同，不足以区分。
// printf(&%d\n&,tmpB);
return tmpB;//否则tmpA那部分数据集合中包含2个不重复的元素，tmpB的那部分数据集合中包含一个不重复的元素，异或结果中相同的数抵消，结果就是tmpB，返回
//返回num从低位开始第一位不为0所对应1左移的结果，如num=10110，则返回00010，如num=110000则返回010000，这里都是用2进制表示
int TheFirst1OfNum(int num)
if(num == 0)
int one = 1;
int i = 0;
for(i=0; i&32; i++)
if(num & one)
one = one&&1;
//找到两个只出现一次的数，通过引用tmpA,tmpB返回。，singleNum为FindSingleNumber函数返回的数组中的一个不重复的元素。
void FindOnceNum(int arr[],int len,int& tmpA,int& tmpB,int singleNum)
invaluedInput =
if(NULL == arr || len&2)
invaluedInput =
int i = 0;
int result = 0;
int tmp = 0;
for(i=0; i& i++)
result ^= arr[i];
/*result与所有数组元素都异或过后，还应该与singleNum异或来抵消FindSingleNumber函数返回的数组中的那个不重复的元素，这样数组就只剩下2个不重复的元素*/
result ^= singleN
//找到第一个不为0的位
tmp = TheFirst1OfNum(result);
//result为0则数组中不存在不重复的元素，输入有误，返回。
if(tmp == 0)
invaluedInput =
//根据result的第一个不为1的位将数组元素分为两部分。
for(i=0; i& i++)
if(arr[i] & tmp)
tmpA ^= arr[i];
tmpB ^= arr[i];
//记得还要将singleNum加进来，才能保证数组中只有2个不同的元素。
if(singleNum & tmp)
tmpA ^= singleN
tmpB ^= singleN
int main()
int arr[] = {1,2,3,4,5,5,7,2,6,7,4};
int len = sizeof(arr)/sizeof(int);
//找到一个不重复的元素
int tmp = FindSingleNumber(arr,len);
int tmpA = 0;
int tmpB = 0;
if(0 == tmp && invaluedInput)
cout&&&invaluedInput&&&
FindOnceNum(arr,len,tmpA,tmpB,tmp);
if(invaluedInput)
cout&&&invaluedInput&&&
cout&&tmp&&endl&&tmpA&&endl&&tmpB&&
另一种简单的解法：如果允许另外开辟空间并且知道数组的最大元素的话，那么可以另外建一个统计数组中元素出现次数的hash表，最后扫面这个hash表，将为1的项输出即可。
看过本文的人也看了：
我要留言技术领域：
取消收藏确定要取消收藏吗？
删除图谱提示你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示你确定要删除该知识节点吗？查看: 356|回复: 39
除了两个数只出现一次外，其余元素都出现两次，找出这两个数？
阅读权限30
在线时间 小时
作者：知乎用户
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
这个题目是说，有一个n个元素的数组，除了一个元素只出现一次外，其他元素都出现两次，让你找出这个只出现一次的元素是几，要求时间复杂度为O(n)且不再开辟新的内存空间。
——————————答案分割线—————————
解法是将所有元素做异或运算，即a[1] XOR&&a[2] XOR a[3] XOR…XOR a[n]，所得的结果就是那个只出现一次的数字，时间复杂度为O(n)。
当时看了答案后就一拍脑瓜，感叹这个技巧真不错。然而直到我遇见了这道题的进阶版，当时真是恍然大悟拍案叫绝。
进阶版:有一个n个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为O(n)且再开辟的内存空间固定(与n无关)。
——————————答案分割线————————
首先，仿照前面的算法，把所有元素异或，得到的结果就是那两个只出现一次的元素异或的结果。
然后，重点来了，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为0，另一个为1，找到这一位。
可以根据前面异或得到的数字找到这一位，怎么找呢？稍加分析就可以知道，异或得到这个数字二进制形式中任意一个为1的位都是我们要找的那一位，找到这一位就可以了(这很容易)。
再然后，以这一位是1还是0为标准，将数组的n个元素分成了两部分，将这一位为0的所有元素做异或，得出的数就是只出现一次的数中的一个;将这一位为1的所有元素做异或，得出的数就是只出现一次的数中的另一个。从而解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。
自己没看懂进阶版解决办法的说明，请问是怎么求出来的？谢谢！
阅读权限30
在线时间 小时
为什么要&忽略寻找不同位的过程&,二进制的位数也会影响循环的次数吧？比如有3个或者更多只出现一次的数。
阅读权限95
在线时间 小时
为什么要&忽略寻找不同位的过程&,二进制的位数也会影响循环的次数吧？比如有3个或者更多只出现一次的数。
【比如有3个或者更多只出现一次的数。】……这个不是题目规定的条件，就不要瞎猜想了。
阅读权限30
在线时间 小时
【比如有3个或者更多只出现一次的数。】……这个不是题目规定的条件，就不要瞎猜想了。
女神，恕我直言：既然是讨论问题，不抓住本质，发现不了规律，一两个例子只能算特殊情况吧。。。
阅读权限95
在线时间 小时
& & & & & & & &
女神，恕我直言：既然是讨论问题，不抓住本质，发现不了规律，一两个例子只能算特殊情况吧。。。
原题目很简单，
利用XOr运算，在m个数中找到缺失的那一个数。
正整数集合1-m，其中缺一个未知数（大小随机），要找出来。
即：在1-m范围内有m-1个数的集合，要找到缺漏的数值n ( 1&=n&=m)
可以有很多种方法，但是有一种特殊的方法，即遍历m-1个数，用XOr运算比较，最后一次的结果就是那个缺失的数。
首先，到这里你能理解这个【算法】成立的原因吗？
如果你已经能理解这个利用XOr算法解这个题目的过程，
那么楼主提出了阶段2的问题：
在数值1-m范围内有2m-2个数，缺失2个数。
即：2m-2个数的集合中，1-m范围内的数都是每个数出现2次，
但其中有任意随机的2个数（n1，n2，n1&&n2）只出现1次。所以一共是2m-2个数。
那么，如何利用XOr运算方法，找出这2个数的数值呢？
这就是楼主要问的问题。
楼主希望你解释一下，如何使用XOr算法找出这2个数，
而不是要求你用其它任何方法解决这个问题，
更不需要你随意更改题目条件，那就完全不是一回事了。
你喜欢思考，那么可以另开帖讨论，但在这里，必须遵循楼主的要求。
阅读权限30
在线时间 小时
本帖最后由 爱疯 于
09:58 编辑
谢谢paciguard、群子老师！
从“可以根据前面异或得到的数字找到这一位，怎么找呢？...”开始，我就看不懂了。比如，
Sub test()
& & Debug.Print &所有的元素：&, 1 Xor 3 Xor 1 Xor 4 Xor 5 Xor 4
& & Debug.Print &一次的元素：&, 3 Xor 5
对照1楼说明，我还是看不懂：这两个数（3和5），是怎么从数组中找出来的？
阅读权限95
在线时间 小时
本帖最后由 香川群子 于
09:35 编辑
先把第1阶段的问题解决代码公布一下：
Sub test1()
& & Dim a&(), i&, k&, m&, n&, r&, r1&, r2&, r3&, t&
& &
& & Randomize '随机种子初始化
& &
'& & m = 10000 '设定m取值范围
& & m = Int(Rnd * 10000) + 10 '随机设定m取值范围
& &
& & n = Int(Rnd * m) + 1 '在1-m范围中随机抽选1个数n
& &
& & ReDim a&(1 To m)
& & k = 0
& & For i = 1 To m
& && &&&If i && n Then k = k + 1: a(k) = i '数组a中填入m-1个数（排除了数值n）
& & Next
& &
& & For i = 1 To m - 1 '数组洗牌法随机乱序
& && &&&r = Int(Rnd * (m - i)) + i
& && &&&t = a(r): a(r) = a(i): a(i) = t
& & Next
& &
& & t = m Mod 4 'm对4求余以便按照规律决定Xor运算的初始化起始值r
& & If t = 0 Then r = m Else If t = 1 Then r = 1 Else If t = 2 Then r = m + 1 Else r = 0
& &
& & For i = 1 To m - 1 '遍历m-1个数
& && &&&r = r Xor a(i) '用Xor算法运算 得到累积结果
& & Next
& & '最后剩余的r 就是缺失的那个数n
& & MsgBox &1-& & m & &中缺失的数 & & n & vbCr & &Xor算法找到的数: & & r
& &
& & 'Xor算法原理：
& & '1-m中所有数位的0/1都是连续分布的,如果有缺失那么Xor会将这个缺失信息遗传下去,直到m-1个数遍历完毕,最后剩下的正好就是缺失数代表的二进制值。
& & '换个角度理解：m开始对1-m所有数的Xor累计结果=0 而其间1-m个数值的顺序可以随机乱序而不影响最终结果。
& & '那么如果把缺失数排在最后1个(第m个数)时,则前面m-1个数的Xor计算结果一定正好和最后一个数抵消（即相同/相等）
& &
End Sub复制代码
阅读权限30
在线时间 小时
原题目很简单，
楼主不过是抛砖引玉罢了，何况这问题也不是楼主自己发明的，已经注明出处，说到讨论和改题目，这是两回事。如果你仔细审题，LeetCode上本身就讨论到1个single number 和 2个 single number的问题，我不过就事论事而已，如果对理解问题有益，就算改题目又如何，学术讨论的风气难道也是独裁专制吗？
阅读权限95
在线时间 小时
本帖最后由 香川群子 于
09:08 编辑
公布进阶2问题的解决代码，解释也加上去了：
Sub test2()
& & Dim a&(), i&, k&, m&, m2&, n1&, n2&, r&, r1&, r2&, t&
& &
& & Randomize '随机种子初始化
& &
& & m = 10000 '设定m取值范围
& & m2 = 2 * m - 2 '总取数个数(每个数出现2次、扣除2个数只出现1次)
& & n1 = Int(Rnd * m) + 1 '第1个随机数值n1
& & n2 = Int(Rnd * (m - 1) + n1) Mod m + 1 '不重复的第2个随机数值n2
'& & n1 = 9: n2 = 84
& &
& & ReDim a&(1 To m2 + 1)
& & For i = 1 To m
& && &&&a(k + 1) = i: a(k + 2) = i '每个数出现2次
& && &&&If i = n1 Or i = n2 Then k = k + 1 Else k = k + 2 'n1/n2只出现1次
& & Next
& &
& & For i = 1 To m2 '数组洗牌法随机乱序
& && &&&r = Int(Rnd * (m - i)) + i
& && &&&t = a(r): a(r) = a(i): a(i) = t
& & Next
& &
& & r = 0
& & For i = 1 To m2 '遍历m2=2m-2个数
& && &&&r = r Xor a(i) '用Xor算法运算 得到累积结果
& & Next
& & '最后剩余的r 就是缺失的n1和n2的累积Xor运算结果
& &
& & k = 0
& & Do
& && &&&If r Mod 2 Then '从个位开始检查=1的数位
& && && && &t = 2 ^ k '该数位相当的整数值 如 1、2、4、8、16、32、64......
& && && && &r1 = 0: r2 = 0 'Xor运算开始值r1/r2初始化
& && && && &For i = 1 To m2 '遍历m2=2m-2个数
& && && && && & If (a(i) And t) = t Then '如果数值a(i)该数位对应=1 则算作第1个数
& && && && && && &&&r1 = r1 Xor a(i) '用Xor算法运算 得到第1个数的累积结果
& && && && && & Else '如果数值a(i)该数位对应=0 则算作第2个数
& && && && && && &&&r2 = r2 Xor a(i) '用Xor算法运算 得到第2个数的累积结果
& && && && && & End If
& && && && &Next
'& && && && &Debug.P r1; r2
& && && && &Exit Do '计算完成后即可退出
& && &&&End If
& && &&&r = r \ 2 '如该数位=0则需继续检查其它=1的数位
& && &&&k = k + 1
& & Loop
& &
& & MsgBox &1-& & m & &中缺失1次的2个数 & & n1 & & / & & n2 & vbCr & &Xor算法找到的2个数 & & r1 & & / & & r2
& &
& & '进阶2问题的Xor算法原理：
& & '1-m中所有数位的0/1也都是连续分布的,如果有缺失那么Xor会将这个缺失信息遗传下去,直到2m-2个数遍历完毕,最后剩下的r 就是缺失的2个数代表的Xor合计二进制值。
& & '那么假设这个r的二进制状态中每1个=1的数位，必定是n1/n2对应数位上的二进制值不同(0/1)所致
& & '因此按此数位把所有2m-2个数分为2类（1/0）各自进行Xor累计运算时，自然就能区分得到2个结果r1/r2对应的结果是n1/n2或n2/n1(顺序可能不同)
& &
& & '这里Xor累计运算查找缺失遗漏值的原理和上面进阶1问题的原理是一样的，即1-m个数值的随机乱序Xor结果=0所以可以倒数第1个值就对应唯一的缺失值。
& & '理解的难点在于，为何用第1次Xor运算的结果r对应任意=1数位 就可以区分n1/n2这2个数。 其实是有几种情况,一开始并不能保证一定得到能够区分2个数的数位。
& & '因此，只需理解为：一定能找到一个数位，使得以这个数位把2m-2个数分为2组时，正好可以把n1/n2分开。这样就可以正确理解进阶2的算法过程了。
& &
End Sub复制代码
阅读权限30
在线时间 小时
楼主不过是抛砖引玉罢了，何况这问题也不是楼主自己发明的，已经注明出处，说到讨论和改题目，这是两回事 ...
谢谢每位回帖的朋友！
请别介意哈，群子老师说话有点怪........... ：(
最新热点 /1
ExcelHome每周都有线上直播公开课，
国内一流讲师真身分享，高手贴身答疑，
赶不上直播还能看录像，
关键居然是免费的！
厚木哥们都已经这么努力了，
你还好意思说学不好Office。
玩命加载中，请稍候
玩命加载中，请稍候
Powered by
本论坛言论纯属发表者个人意见，任何违反国家相关法律的言论，本站将协助国家相关部门追究发言者责任！ & & 本站特聘法律顾问：徐怀玉律师 李志群律师下次自动登录
现在的位置:
& 综合 & 正文
每天一道算法题-1 找出数组中两个只出现一次的数字
由于做项目，还有看论文，很长时间没有接触过题了，今天看到博客园里小桥流水的算法文章，感觉很简单，但编写的时候竟然发现不知道怎么操作字符串数组了。算法还是要每天练习啊，这样才不会退步。有感于此，以后每天（节假日得陪老婆，就放过了吧^_^）都会写一道算法题，以保持自己的水平。我搜集的算法题在文章最后都会有作者的版权声明，但不一定是作者原来的解决方法，自己会做相应的优化。
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
可能大家都见识过找出一个只出现一次的数，直接把所有的数异或就可以了，最终的结果就是这个数了。但是如果出现两个这样的数，那又将如何呢？
假如这两个数为a和b，那么将所有的数异或得到的数必定为a^b。由于a和b不相等，那么a^b != 0，也就是说在a^b中必定至少有一位为1，对应位上a与b不一样，根据这一位，我们可以将a和b分开，并将数分成两组。注意，两个相同的数肯定会被分到同一个组。这样，分别对每一组进行取异或，就能求出这两个数了。
* Author: zhuxiaoyang
* Created on 日，下午16:00
#include &iostream&
int findOutOneOdd(int a[], int n)
int result = a[0];
for(int i = 1; i & ++i)
result ^= a[i];
void findOutTwoOdds(int a[], int n, int &odd1, int &odd2)
int x = findOutOneOdd(a, n);
int y = 1;
while(y &= x)
for(int i=0; i&n; ++i)
if(y & a[i])
odd1 ^= a[i];
odd2 ^= a[i];
int main()
int A[]={4, 5, 3, 4, 5, 7, 7, 6, 8, 8};
int num = sizeof(A)/sizeof(int);
int odd1 = 0, odd2 = 0;
if(num%2 != 0)
throw "input is illegle";
findOutTwoOdds(A, num, odd1,odd2);
cout&&odd1&&" "&&odd2&&
system("pause");
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
&&&&推荐文章:
【上篇】【下篇】一个数组有除了两个元素只出现一次，其他元素全部都出现了两次，请找出只出现一次的两个元素，并输出 - sinat_的博客 - CSDN博客
一个数组有除了两个元素只出现一次，其他元素全部都出现了两次，请找出只出现一次的两个元素，并输出
#include &stdio.h&
#define N 10
int main()&
int a[N] = {1,2,7,99,3,3,4,1,2,4}, flat[N] = {0};
int i, j, sum = a[0], last_bit = 0, sum0 = 0, sum1 = 0;
// 对数组中所有元素进行异或操作
// 如果当数组中只有一个元素只出现一次时，则异或的结果就是只出现一次那个元素&
for(i = 1; i & N; i ++)
sum = sum ^ (a[i]);
// 如果当数组中有两个元素只出现一次时，则将上述异或的结果转化成二进制，并从右到左进行判断，将第一个为 1的位置记录为 i&
for(i = 0; last_bit != 1; i ++)
last_bit = sum & 1;
sum = sum && 1;
// 接着对所有的元素的二进制形式的第 i位进行扫描，将结果记录到 flat数组
// flat[j]=1表明第 j元素的第 i位为 1，否则为 0&
for(j = 0; j & N; j ++)
flat[j] = (a[j] && (i-1)) & 1;
// 根据上述循环得到的 flat数组，对所有元素进行分组
// 结果为 1的在一起进行异或操作，为 0的在一起进行异或操作 ，两组异或的结果就是两个只出现一次的元素&
for(j = 0; j & N; j ++)
(flat[j] == 1) ? (sum1 = sum1 ^ (a[j])) : (sum0 = sum0 ^ (a[j]));
printf(&%d %d\n&, sum0, sum1);
我的热门文章给一组数，只有两个数只出现了一次，其他所有数都是成对出现的。怎么找出这两个数
本文给出两种算法，（编译环境Visual Studio 2013）
1.遍历整个数组，并记录每个数出现的次数，然后输出只出现一次的数。
2.对于出现了奇数次的数，使用疑惑即可。
#include&stdio.h&
#include&stdlib.h&
void find_f(int arr[], int len)
//寻找单独数
printf(&这一组数中单独的数有：&);
for (i = 0; i & i++)
for (j = 0; j & j++)
if (arr[j] == arr[i])
//如果两数相同，k++
if (k == 1)
printf(&%d &,arr[i]);
如果（k=1）,即这个数只出现过一次，则输出
printf(&\n&);
int main()
int arr[] = { 4, 2, 6, 4, 5, 5, 3, 6 };
//数组初始化，可自由赋值
int len = sizeof(arr) / sizeof(arr[0]);
//求数组长度
find_f(arr, len);
//函数调用
system(&pause&);
本方法求很严重的缺点就是，时间复杂度高，不够优化。
方法二：（本方法参考了&夜的寂寞&发表在51CTO的博客，博客地址：https://.）
一组数中，只有一个数只出现了奇次，其他所有数都是成对出现的，找出出现奇次数的数。对于这个题，我们只需对所有数及逆行异或即可。异或公式：
a&(b&c)=(a&b)&c
如果只有一个数是单独出现的，代码如下：
#include &stdio.h&
#include &stdlib.h&
int main()
int arr[] = { 1, 2, 3, 4, 1, 2, 3 };
int ret = 0;
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i & i++)
ret ^= arr[i];
printf(&出现奇数次的数为:& %d\n&, ret);
system(&pause&);
同理，如果有偶数个数出现里一次，那么整组数异或的结果就是这两个数的的异或结果，那么这个异或结果中，在它的二进制表示中为0的位说明两个数在此位的二进制表示相同，同样的如果此位为1，说明两个数在此位的二进制不同。
为了达到与上述代码相同的效果，我们将这组数分为两组，然后使用上述方法，即可简便的分辨出来只出现一次的数。
只要我们把这组数分开，分为两组数，再分别利用异或，就可以得那两个数。
现在我们看如何将一组数分为每一组数都只有一个数出现过一次的两组数：首先我们对所有数进行异或，那么得到的就是两个出现奇次的那两个数的异或，比如{ 1, 2, 3, 4, 1, 2, 7, 3 }，就得到7&4，这个数肯定不为0，我们找出这个数的二进制数的最右边的1(设最右边的1在第inter位)，然后找出数组的每个元素的第inter位，并判断此位是1还是0，是1的为一组，是0的为一组，这样就分好了组，再利用上面的例子，就可得到出现奇数次的那两个数。
#include &stdio.h&
#include &stdlib.h&
int main()
int arr[] = { 1, 2, 3, 4, 1, 2, 7, 3 };
int len = sizeof(arr) / sizeof(arr[0]);
int ret = 0;
int inter = 0;
int retA = 0;
int retB = 0;
for (int i = 0; i & i++)
ret ^= arr[i];
/*找ret最右边的1*/
inter = ret - (ret&(ret - 1));
for (int i = 0; i & i++)
int a = (arr[i] && (inter - 1)) % 2;
//取出arr[i]的第inter位
if (a == 0)
retA ^= arr[i];
retB ^= arr[i];
printf(&出现奇数次的两个数为:& %d,%d\n&, retA, retB);
system(&pause&);
本人还在学习进步中，代码肯定有很多疏漏之处，欢迎各位大神批评指正。以助于我更好的进步。}