class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { if(data.size()<2) return ; int size=data.size(); int temp=data[0]; for(int i=1;i<size;i++) temp=temp^data[i]; if(temp==0) return ; int index=0; while((temp&1)==0){ temp=temp>>1; ++index; } *num1=*num2=0; for(int i=0;i<size;i++) { if(IsBit(data[i],index)) *num1^=data[i]; else *num2^=data[i]; } } bool IsBit(int num,int index) { num=num>>index; return (num&1); } };
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { if(data.size()<2) return ; int size=data.size(); int temp=data[0]; for(int i=1;i<size;i++) temp=temp^data[i]; if(temp==0) return ; int index=0; while((temp&1)==0){ temp=temp>>1; ++index; } *num1=*num2=0; for(int i=0;i<size;i++) { if(IsBit(data[i],index)) *num1^=data[i]; else *num2^=data[i]; } } bool IsBit(int num,int index) { num=num>>index; return (num&1); } };
可以用位运算实现,如果将所有所有数字相异或,则最后的结果肯定是那两个只出现一次的数字异或的结果,所以根据异或的结果1所在的最低位,把数字分成两半,每一半里都还有只出现一次的数据和成对出现的数据
这样继续对每一半相异或则可以分别求出两个只出现一次的数字