首页 > 代码库 > 找出数组中两个只出现一次的数字 【微软面试100题 第六十一题】
找出数组中两个只出现一次的数字 【微软面试100题 第六十一题】
题目要求：
一个整型数组里除了两个数字机之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度O(N).空间复杂度O(1).
参考资料：剑指offer第40题。
题目分析：
已知：
1.两个相同的数字异或的结果为0，即a^a = 0.
2.两个不相同的数字异或的结果的二进制中某一位为1，则这两个数字的二进制中对应位一个为0，一个为1.如3^2 = 1,对于最低位的二进制，3的最低位二进制为1，2的最低位二进制位0，则结果1的最低位二进制肯定为1.
假设原数组中只出现一次的两个数为a和b，则，原数组所有元素异或的结果c,即为a^b的结果(因为其他异或都为0)，即a^b = c;
根据已知条件2，我们从c中找到其二进制中为1的位，把原数组分成两个部分X和Y(a和b分别在X和Y中，且X和Y中分别都是只有一个数字出现一次，其他数字出现两次)，则X中的所有元素异或的结果肯定为a，Y中所有的元素异或的结果肯定为b，即为所求。
代码实现：
#include <iostream>using namespace std;const int N = 6;bool FindNumsAppearOnce(int data[],int len,int &num1,int &num2);int main(void){ int data[N] = {4,2,6,2,4,5};// int data[N] = {4,2,6,2,4,6}; int num1,num2; if(FindNumsAppearOnce(data,N,num1,num2)) { cout << "num1 = "<< num1 << ",num2 = " << num2 << endl; } else cout << "不满足情况" << endl; return 0;}unsigned int FindFirstBitIs1(int num){ int index = 0; while((num&1)==0 &&(index<8*sizeof(int))) { num >>= 1; ++index; } return index;}bool IsBit1(int num,unsigned int index){ num >>= index; return (num&1);}bool FindNumsAppearOnce(int data[],int len,int &num1,int &num2){ if(data=http://www.mamicode.com/=NULL || len<2 || ((len&0x01)==1)) return false; int result =0; for(int i=0;i<len;i++) result ^= data[i]; if(result==0) return false; unsigned int index = FindFirstBitIs1(result); num1 = num2 = 0; for(int j = 0;j<len;j++) { if(IsBit1(data[j],index)) num1 ^= data[j]; else num2 ^= data[j]; } return true;}
找出数组中两个只出现一次的数字 【微软面试100题 第六十一题】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。