题目描述
- 一个整型数组里除两个数字之外，其他数字都出现了两次
- 请写程序找出这两个只出现一次的数字
- 要求时间复杂度是 O(n)，空间复杂度为 O(1)
题目解读
- 剑指Offer 275
- 运用异或运算的一个性质：任何一个数字异或它自己都等于0。也就是说我们从头到尾依次异或数组中的每个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些成对出现两次的数字全部在异或中抵消了
- 下面就是要把数组分为两个子数组，每个子数组中包含一个只出现一次的数字，而其他数字成对出现，如果能这样划分，我们就能按照前面的方法分别找出两个只出现一次的数字啦
- 我们还是从头到尾异或数组中的数字，则最终得到的结果就是两个只出现一次的数字的异或结果，因为其他数字出现了两次，在异或中全部抵消了。由于这两个数字肯定不一样，则异或结果肯定不为0。在这个结果的二进制中至少有一位为1。我们在这个数字中找到第一个为1的位的位置，记为第n位。我们现在以第 n 位是不是 1 为标准把原数组中的数字分为两个子数组
代码
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int length = data.size();
if(length < 2){
return ;
}
int result = 0;
for(int i=0; i < length; i++){
result ^= data[i];
}
int indexOf1 = FindIndexOf1(result);
*num1 = *num2 = 0;
for(int i=0; i < length; i++){
if(IsIndexOf1(data[i], indexOf1)){
*num1 ^= data[i];
}
else{
*num2 ^= data[i];
}
}
}
int FindIndexOf1(int result){
int indexOf1 = 0;
while((result & 1) == 0 && indexOf1 < 8*sizeof(int)){
result = result >> 1;
indexOf1 += 1;
}
return indexOf1;
}
bool IsIndexOf1(int number, int indexOf1){
number = number >> indexOf1;
return number & 1;
}
};
int main(){
int a[10] = {2, 3, 4, 6, 3, 2, 5, 5};
int len = 8;
int num1,num2;
vector<int> data;
Solution ss;
for(int i=0; i < len; i++){
data.push_back(a[i]);
}
ss.FindNumsAppearOnce(data, &num1, &num2);
cout<<num1<<" "<<num2<<endl;
}
总结展望
