【 声明：版权所有，转载请标明出处，，请勿用于商业用途。 联系信箱：libin493073668@sina.com】
题目链接：?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目描述一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。思路这道题一开始要想到最好的解法很难，如果使用排序的话时间复杂度并不好，那么我们怎么才能使用最好的复杂度来解决呢？首先我们先考虑怎么找只有一个数字出现一次的状况，我们可以通过异或运算，一遍下来得到的异或值就是只出现一次的数值。那么如果有两个数字只出现一次呢？我们可以知道这两个数字必然是不同的，那么我们一遍异或下来的值必然是这两个数的异或值，然后我们可以使用这个异或值来把整个数组划分为两个区间。我们首先找到异或值最右边的1出现的位置，对于这个位置而言，我们要求的这两个数在这个位置必然是不同的，那么我们就可以将数组分为两部分，使得要求的这两个数分别在这两个区间里面，然后我们再分别进行异或就可以了。而我们知道，对于X&(-X)所求的，正式X最右边的1所处的位置得到的值。
class Solution{public:void FindNumsAppearOnce(vector<int> data,int* num1,int *num2){int len = data.size();if(len<2)return;int Xor = 0;for(int i = 0; i<len; i++)Xor^=data[i];Xor = Xor&(-Xor);*num1 = *num2 = 0;for(int i = 0; i<len; i++){if(data[i]&Xor)*num1^=data[i];else*num2^=data[i];}}};
版权声明：本文为博主原创文章，如果转载，请注明出处
一直想去旅行，去很美很美的地方，但往往真正踏足想去的地方，
