数组中只出现一次的数字
题目描述
题目链接：?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
首先题目里有个很关键的信息：除了两个数字之外，其他的数字都出现了两次。作为这题的突破口！
那么先来想想这样的情况，一个数组中，除了一个数，其他数都出现偶数次的情况！
看这题目的信息，就是透露你要用异或来求解的嘛，（偶数次异或为0），所以我们只要把整个数组都异或一次就可以解决问题了。
那么现在来想2个数的情况，有人说也都异或一遍不就好了。可是这样就得到了我们要求的那两个数的异或后的结果了，而不能得到要求的那2个数，所以还差一点点；
考虑这样一个数组：1 1 2 3 34 4 5 6 6 发现如果要求2个数分别位于2个数组中，那么2个数组分别异或就能得到解不是吗？！ 就好好像两个问题一组合成问题二一样，（思想没错！）
我们知道现在最主要的问题是把原数组拆成2个问题一的数组。（eg：1 2 3 4 5 1 2 3）
这里有个小技巧：因为相同数字异或为0，不同数字异或不为0，所以结果一定不是0；设异或结果为ans，那么我们可以找到ans的二进制某一位一定为1，so。。这一位一定来自num1或者num2；所以以这一位为分界条件，，把数组分成2部分，eg：ans=1；数组分成{1，3，5，3，1}和{2，4，2} 这样每个数组再异或就可以得到解了！
#include<stdio.h>#include<vector>using namespace std;class Solution {public:void FindNumsAppearOnce(vector<int> data,int *num1,int *num2) {if(data.size()<2) return ;int ans=data[0];int len=data.size();for(int i=1;i<len;i++){ans^=data[i];}if(ans==0) return ;//没有两个不一样的int f=1;for(int i=1;;i++){if(f&ans) break;f=1<<i;}//printf("%d\n",f);*num1=0;*num2=0;for(int i=0;i<len;i++){if(f&data[i]){*num1^=data[i];}else{*num2^=data[i];}}}};int main(){vector<int> arr(10);arr[0]=1;arr[1]=2;arr[2]=3;arr[3]=4;arr[4]=5;arr[5]=1;arr[6]=2;arr[7]=3;arr[8]=7;arr[9]=7;Solution so;int a;int b;int *num1=&a;int *num2=&b;so.FindNumsAppearOnce(arr,num1,num2);printf("%d\t%d\n",*num1,*num2);return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
成功是奋斗的结果，而奋斗是成功的必经之路。
