04求数组中只出现一次的两个数字。
一个整型数组里除了两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求是否复杂
我们想到异或运算的一个性质:任何一个数字异或他自己都等于0。也就是说,如果我们从头到尾依次异或数组中的每个数字,那么最终结果刚好是那个只出现一次的数字,那些出现两次以上的数字全部在异或中抵消了。可这道题目是有两个只出现一次的数字。怎么拆成两个子数组呢?我们先遍历数组全部异或一遍,得到的结果就是那两个数字的异或结果,由于这两个数字不同,所以异或结果不为0,在二进制中至少有一位为1,那么我们就可以根据这一位是不是为1,把数字划分成两个子数组,然后就能求解了。而且相同的数不可能分别分配到两个子数组中,因为它们的二进制也是相同的。#include<bits/stdc++.h>usingnamespacestd;voidfindOnce(int*a,intlen){if(a==nullptr||len<=0)return;intXOR=0;for(inti=0;i<len;i++)//求异或值XOR^=a[i];intidx=0;while((XOR&1)==0){//求最右的1XOR>>=1;idx++;}intn=0,m=0;//两个子数组分别异或for(inti=0;i<len;i++){if(((a[i]>>idx)&1)==0)n^=a[i];elsem^=a[i];}printf("%d%d",n,m);}intmain(){inta[8]={2,4,3,4,6,3,5,2};findOnce(a,8);return0;}//运行结果:65
来自:容器和Map-数组和链表