【剑指Offer】题40：数组中只出现一次的数字（出现2次）

题目描述：

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

输入：

每个测试案例包括两行：

第一行包含一个整数n，表示数组大小。2<=n <= 10^6。

第二行包含n个整数，表示数组元素，元素均为int。

输出：

对应每个测试案例，输出数组中只出现一次的两个数。输出的数字从小到大的顺序。

样例输入：

8
2 4 3 6 3 2 5 5

样例输出：

4 6

解法：相同的数字异或为零，那么最后得到的结果一定是2个不同数字异或的结果x。利用这个原理，而异或得到数字中某位1一定是两个这一位是1和0，我们从x低位找到第一个1，然后将数组按照这一位是否为1分成2个数组，这时候2个不同的数字一定是分别分到这个2个数组中，而每个数组中的数字肯定是成对出现的（因为如果不是成对出现是因为2个相同的数字不会有一位是既是0又是1而分到不同的数组中）。

附上OJ AC代码，（********之前在九度练习的时候，老是报运行时错误！那是因为，我经常不把用到的临时变量在while(scanf()!=EOF)中初始化！这点是大忌！！！）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int findFirst1(int x) {
int t = 0;
while((x & 1) == 0) {
x>>=1;
t++;
}
return t;
}
int Move2Number(int x,int t) {
x = x >> t;
return (x&1);
}
int main() {
int n,i,x,t,temp1=0,temp2=0;
int *a=NULL,*left=NULL,*right=NULL,i1=0,j1=0;
while(scanf("%d",&n)!=EOF) {
i1 = 0 ; //分类累加标记
j1 = 0 ;
a=(int*)malloc(n*sizeof(int));
left=(int*)malloc(n*sizeof(int));//左右分类数组
right=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++) {
scanf("%d",&a[i]);
}
x=a[0];
for(i=1;i<n;i++) {
x^=a[i];
}
if(x==0)return 0;
t=findFirst1(x);//从低位开始找到第一个为1的位
for(i=0;i<n;i++) {
if(Move2Number(a[i],t))left[i1++]=a[i];//按照该位是否为1进行分类
else right[j1++]=a[i];
}
x=left[0];
for(i=1;i<i1;i++) {
x^=left[i];//左边数组找到第一个不同的数字
}
temp1=x;
x=right[0];
for(i=1;i<j1;i++) {
x^=right[i];//右边数组找到第二个不同的数字
}
temp2=x;
if(temp1<temp2)printf("%d %dn",temp1,temp2);
else printf("%d %dn",temp2,temp1);
free(a);
free(left);
free(right);
}
return 1;
}
/**************************************************************
Problem: 1351
User: tcals
Language: C
Result: Accepted
Time:800 ms
Memory:11460 kb
****************************************************************/

最后

以上就是无心书包为你收集整理的【剑指Offer】题40：数组中只出现一次的数字（出现2次）的全部内容，希望文章能够帮你解决【剑指Offer】题40：数组中只出现一次的数字（出现2次）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。