C++版 - 剑指Offer 面试题40：数组中只出现一次的两个数 题解
C++版 - 剑指Offer 面试题40：数组中只出现一次的两个数 题解
面试题40：数组中只出现一次的两个数
提交网址： http://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811?tpId=13&tqId=11193
或 http://ac.jobdu.com/problem.php?pid=1351
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
牛客网OJ的输入输出接口是：void FindNumsAppearOnce(vector<int> data,int* num1,int *num2)，其中data是待查找的整型数组，而num1和num2是分别指向两个数的指针，返回值为*num1和*num2，要求原址进行，返回值为void类型。
输入：
每个测试案例包括两行：
第一行包含一个整数n，表示数组大小。2<=n <= 10^6。
第二行包含n个整数，表示数组元素，元素均为int。
输出：对应每个测试案例，输出数组中只出现一次的两个数。输出的数字从小到大的顺序。九度OJ 样例输入：8 2 4 3 6 3 2 5 5 样例输出：4 6
分析：
按位异或^具有如下性质：
1. 任何一个数字异或它自身都等于0。
2. 异或满足恒等式(a^b)^b=a，这还可以用来作变量值的快速交换，虽然本题不需要作变量值的交换。
故用两次异或运算特点可以解决此问题：
(1) 先从头到尾依次异或原数组中的每一个数字，那么最终的结果刚好只出现一次的数字的异或结果，因为成对出现的两次的数字全部在异或中抵消了。 (2) 原数组中有两个数字只出现一次，且两个只出现一次的数肯定不相等，它们的异或结果一定不为0，一定有一个数在某位(记作倒数第k位)上有1，另外一个数的此位上没有1。因此我们想办法把原数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，一个子数组的此位上一定有1，另个子数组的此位上一定没有1，然后分别对每个子数组求异或，因为划分后的两个子数组有这样的特点：其他数都出现两次，只有一个数只出现一次。因此，我们可以再次运用按位异或运算，分别得到两部分只出现一次的数。
AC代码：
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) // 返回值的大小顺序没作要求，输入的数组也不一定是有序的
{
if(data.size()<2) return ; // 返回值为void类型，出口应该这样写
int partFlag=0x1; // partFlag为两类数的划分标志，是可变的
int xorRes=0;
for(int i=0; i<data.size();i++)
xorRes ^= data[i];
*num1 = xorRes;
*num2 = xorRes;
while((xorRes & partFlag)==0)
partFlag <<= 1; // a & 0x1 等价于a%2，在这用来判断最后一位是0还是1，
// 找到xorRes中的1个位置时，partFlag的最高位(倒数第k位)是1，其他位全0
for(int i=0; i<data.size();i++)
{
if((data[i] & partFlag)==0) *num1 ^= data[i]; // 判断data数组中所有数的倒数第k位是0还是1，*num1是两单次出现的数中的较大者
else *num2 ^=data[i]; // *num1是两单次出现的数中的较大者, *num2是较小者
}
}
};
// 以下为测试
int main()
{
vector<int> data1 = {3,1,10,1,3,6,2,6};
int* num1 = new int;
int* num2 = new int;
Solution sol;
sol.FindNumsAppearOnce(data1, num1, num2);
cout<<*num1<<" "<<*num2<<endl;
return 0;
}此题有个简化版：
136. Single Number
提交网址：https://leetcode.com/problems/single-number/
Total Accepted: 127018 Total Submissions: 255025 Difficulty: Medium
Given an array of integers, every element appears twice except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
AC代码：
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums)
{
if(nums.size()<1) return 0;
int res, xorRes=0;
for(int i=0; i<nums.size();i++)
xorRes ^= nums[i];
res = xorRes;
return res;
}
};
int main()
{
vector<int> data1 = {3,1,10,1,3,6,6};
Solution sol;
int res1=sol.singleNumber(data1);
cout<<res1<<endl;
return 0;
}