[剑指Offer]40.数组中只出现一次的数字
程序员文章站
2022-07-15 10:29:21
...
题目
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路
我们直到异或的性质：
任何一个数字异或他自己都等于0.
所以说我们如果从头到尾依次异或每一个数字，那么最终的结果刚好只出现一次的数字，因为成对出现的两次的数字全部在异或中抵消了。
这道题中有两个数字只出现一次。这样的话我们得到的结果就是这两个数字的异或结果。因此我们想办法把原数组分成两个子数组，使得每个子数组包含一个只出现一次的数字。这样我们就可以对这两个子数组分别异或，就能得到两个只出现一次的数字。
现在问题是怎样把原数组分成两个子数组，使得每个子数组包含一个只出现一次的数字？
由于异或的结果肯定是那两个只出现一次的数字的异或结果，所以异或结果肯定不为0，也就是说这个结果二进制表示中至少有一位是1。我们可以找到第一个为1的下标位置（记为第n位）作为划分数组的依据。第一个子数组中每个数的第n位为1，第二个子数组的每个数的第n位为0。对于出现两次的数肯定分在同一个子数组中。那两个只出现一次的数字分别分在不同的子数组中。
假设数组为｛2,4,3,6,3,2,5,5｝，异或结果为2，二进制表示为0010。异或得到的结果中倒数第二位为1，于是我们根据倒数第二位是不是为1分为两个子数组。第一个子数组｛2，3，6，3，2｝，其中所有数字的倒数第二位为1；第二个子数组｛4，5，5｝，其中所有数字的倒数第二位为0。接下来只要分别对这两个子数组求异或，就能找出第一个子数组中只出现一次的数字为6，第二个子数组中只出现一次的数字为4。
代码
/*---------------------------------------
* 日期：2015-04-26
* 作者：SJF0115
* 题目: 40.数组中只出现一次的数字
* 网址：http://www.nowcoder.com/books/coding-interviews/e02fdb54d7524710a7d664d082bb7811
* 结果：AC
* 来源：剑指Offer
* 博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int size = data.size();
if(size <= 1){
return;
}//if
int result = data[0];
// 所有数XOR
for(int i = 1;i < size;++i){
result ^= data[i];
}//for
// 二进制中第一个为1的下标
int index = 0;
while((result != 0) && ((result & 1) == 0)){
result >>= 1;
++index;
}//while
result = (1 << index);
*num1 = 0;
*num2 = 0;
for(int i = 0;i < size;++i){
// 第index位为1
if((data[i] & result) > 0){
*num1 ^= data[i];
}//
else{
*num2 ^= data[i];
}//else
}//for
}
};
int main(){
vector<int> num = {3,1,10,1,3,6,2,6};
int* num1 = new int(0);
int* num2 = new int(0);
Solution s;
s.FindNumsAppearOnce(num,num1,num2);
cout<<*num1<<" "<<*num2<<endl;
return 0;
}