題目
一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外臼膏，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫(xiě)程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字示损。
解題思路
對(duì)于一個(gè)簡(jiǎn)單的問(wèn)題：找出數(shù)組中只出現(xiàn)一次的數(shù)字渗磅，我們使用異或操作對(duì)出現(xiàn)兩次的數(shù)字進(jìn)行抵消，最后的結(jié)果就是只出現(xiàn)一次的數(shù)組检访。
對(duì)于這個(gè)問(wèn)題始鱼，我們可以把數(shù)字分成兩個(gè)數(shù)組，各自包含一個(gè)只出現(xiàn)一次的數(shù)字脆贵。但是這個(gè)怎么劃分医清？
我們先對(duì)數(shù)組進(jìn)行全部的異或操作，得到的結(jié)果卖氨，找到結(jié)果中二進(jìn)制第一次出現(xiàn)1的位置会烙，記錄下來(lái)，然后把這個(gè)位置是1的數(shù)字劃分為第一的數(shù)組筒捺，對(duì)于這個(gè)位置的數(shù)字是0的數(shù)組柏腻，為第二個(gè)數(shù)組，進(jìn)行異或系吭，得到的兩個(gè)數(shù)組就是我們所需要的五嫂。
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
if(data.size() < 2)
return;
unsigned int indexof1 = findFirstBit1(data);
*num1 = 0;
*num2 = 0;
for(int i = 0; i < data.size(); i++){
if(bitIs1(data[i], indexof1)){
*num1 ^= data[i];
}else{
*num2 ^= data[i];
}
}
}
unsigned int findFirstBit1(vector<int> data){
int resultExclusiveOR = 0;
for(int i = 0; i < data.size(); i++){
resultExclusiveOR ^= data[i];
}
int indexBit1 = 0;
while((resultExclusiveOR & 1) == 0 && (indexBit1 < 8*sizeof(resultExclusiveOR)))
{
resultExclusiveOR = resultExclusiveOR >> 1;
indexBit1++;
}
return indexBit1;
}
bool bitIs1(int num, unsigned int indexBit1){
num = num >> indexBit1;
return (num & 1);
}
};
