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

92 阅读 0 评论 61 点赞

我是靠谱客的博主寂寞世界，最近开发中收集的这篇文章主要介绍【剑指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
****************************************************************/