一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
数组中只出现一次的数字
http://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
if(data.size()<2)return;
int resultExclusiveOr = 0;
for(int i = 0; i < data.size();i++){
resultExclusiveOr ^= data[i];
}
int indexof = FindFirstBitIs(resultExclusiveOr);
*num1 = *num2 = 0;
for(int j = 0 ;j < data.size();j++){
if(isBit(data[j],indexof)){
*num1 ^= data[j];
}else{
*num2 ^= data[j];
}
}
}
int FindFirstBitIs(int num){
int indexBit = 0;
while(((num & 1) ==0 )&& (indexBit < (8 * sizeof(int)))){
num >>= 1;
indexBit++;//to Mark the number of the place where an exception has started
}
return indexBit;// to return the place
}
bool isBit(int num,int indexBit){
num>>=indexBit;//to judge the mark place inoder to separate the numbers
return num & 1;
}
};
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
if(data.size()<2)return;
int resultExclusiveOr = 0;
for(int i = 0; i < data.size();i++){
resultExclusiveOr ^= data[i];
}
int indexof = FindFirstBitIs(resultExclusiveOr);
*num1 = *num2 = 0;
for(int j = 0 ;j < data.size();j++){
if(isBit(data[j],indexof)){
*num1 ^= data[j];
}else{
*num2 ^= data[j];
}
}
}
int FindFirstBitIs(int num){
int indexBit = 0;
while(((num & 1) ==0 )&& (indexBit < (8 * sizeof(int)))){
num >>= 1;
indexBit++;//to Mark the number of the place where an exception has started
}
return indexBit;// to return the place
}
bool isBit(int num,int indexBit){
num>>=indexBit;//to judge the mark place inoder to separate the numbers
return num & 1;
}
};
这道题中,*num1 和 *num2是返回的两个值。
在这个数组中有两个数是只出现一次。
将这个数组中的数进行全部的异或。因为相同的数字异或等于0,任何数字和0进行异或还等它本身。
这个数组中的所有的数字进行异或之后,得到的值就是那两个不相同的数字异或的结果,因为相同的数字异或都进行抵消了。
对得到的结果进行判断其二进制从第几位开始是1,依据这一位,将这两个数字进行划分到不同的两类中,然后进而也可以将数组中的全部数字都按照这个分类法则进行分类。
数组中的数按照这个分类法则将数字分为了两类,将每一类中的数字进行全部的异或,得到的结果就是其中的一个数字。共两类,就得到了两个数字的结果。