一個整型數(shù)組里除了兩個數(shù)字之外衬鱼，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字捻悯。
這道題呢在leetcode上見過匆赃，那道題是從1連續(xù)到n，中間缺了一個數(shù)今缚，讓你找出來缺的那個數(shù)是什么算柳。這兩道題很相似，那道題就是用了疑惑姓言，數(shù)組中的每個數(shù)和從1開始的i抑或瞬项，這樣剩下來的也就是單獨出現(xiàn)的i，也就是數(shù)組中缺少的那個元素何荚。
講真囱淋，我看到這道題的時候完全沒有想到用異或，而且得知是兩個不一樣的元素的時候也不知道怎么樣去用異或餐塘。所以所算法妥衣，對于一般人來講，就是見過戒傻，用的熟練的問題税手，不求你會發(fā)明創(chuàng)造，只要用的好就可以了需纳。
扯遠了芦倒，回到這道題上。這道題有兩個單獨出現(xiàn)的元素不翩。如果使用異或走一遍這個數(shù)組的話得到的結(jié)果是非0的兵扬，也就是這兩個元素異或的結(jié)果。那么根據(jù)這個結(jié)果口蝠，怎么找出這兩個元素呢器钟。
思考一下，兩個不一樣的元素的異或的結(jié)果肯定不是0亚皂。那么我們就找這個結(jié)果中有右往左第一個非0位俱箱，也就是1出現(xiàn)的第一次的位置国瓮。這兩個元素中肯定有一個在這個位置是0灭必，另一個在這個位置是1。而其他成對出現(xiàn)的元素也會分為兩個部分乃摹，一個部分在個位置是1禁漓，另一個部分在這個位置是0.所以，我們就把一個數(shù)組求兩個單獨元素的問題就分割成孵睬，兩個數(shù)組每個數(shù)組求其單獨元素的問題播歼。所以這個時候使用異或就很好解決了。
代碼如下：
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
if(data.size() <2)return;
int hxor =0;
int flag =1;
for(int i=0;i<data.size();++i)
hxor ^= data[i];
while((hxor&flag)==0) flag <<= 1;
*num1 = hxor;
*num2 = hxor;
for(int i=0;i<data.size();++i)
{
if(data[i] & flag)
*num1 ^= data[i];
else
*num2 ^= data[i];
}
}
};
