剑指Offer（四十）数组中只出现一次的数（Java版 )

清疚 2021-09-27 00:06 183阅读 0赞

# 一、题目描述 #

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

# 二、题目分析 #

## Step1： ##

首先，看下这个问题的简化版：  
很多成对出现数字保存在磁盘文件中，注意成对的数字不一定是相邻的，如2, 3, 4, 3, 4, 2……，由于意外有一个数字消失了，如何尽快的找到是哪个数字消失了？  
这里可以利用异或运算的特性。自己与自己相异或得0，自己与0相异或得自己。  
先来测试下这个找出那个消失的数：

public class Test4 {
        public static void main(String[] args) {
            int array[] = {
       1, 347, 6, 9, 13, 65, 889, 712, 889, 347, 1, 9, 65, 13, 712};  
            int lostNum = 0;  
            for (int i = 0; i < array.length; i++)  
                lostNum ^= array[i];  
            System.out.println("缺失的数字为: "+lostNum);     
        }
    }

运行结果：  
缺失的数字为: 6

## Step2： ##

现在分析有两个数都小数了的情况，也就是本题。  
设题目中这两个只出现1次的数字分别为A和B，如果能将A，B分开到二个数组中，那显然符合“异或”解法的关键点了。因此这个题目的关键点就是将A，B分开到二个数组中。由于A，B肯定是不相等的，因此在二进制上必定有一位是不同的。根据这一位是0还是1可以将A，B分开到A组和B组。而这个数组中其它数字要么就属于A组，要么就属于B组。再对A组和B组分别执行“异或”解法就可以得到A，B了。而要判断A，B在哪一位上不相同，只要根据A异或B的结果就可以知道了，这个结果在二进制上为1的位都说明A，B在这一位上是不相同的。

public class Test4 {
        public static void FindNumsAppearOnce(int[] arr)  
        {  
            int len = arr.length;
            if(len < 2)  
                return;  
            int i;  
            int AllXOR = 0;  
            //全部异或 ,得到异或的结果
            for(i = 0;i < len;i++)  
                AllXOR ^= arr[i];  
            //找出第几位为1，如010，根据这一位的不同将数组分为两组
            int res = FindFirstBit1(AllXOR);  
            int num1=0, num2 = 0;  
            for(i = 0;i < len;i++)  
            {  //分成了两组
                if(IsBit1(arr[i],res))  
                    num1 ^= arr[i];   //第一组异或的结果是我们要找的那个数 
                else  
                    num2 ^= arr[i];   //第二组异或的结果是我们要找的那个数 
            }  
            System.out.println(num1+"and"+num2);
        }
        //返回num的最低位的1，其他各位都为0 
        public static int FindFirstBit1(int num)  
        {  
            //二者与后得到的数，将num最右边的1保留下来，其他位的全部置为了0 
            return num & (-num);  
        }  
    
        /* 判断data中特定的位是否为1， 这里的要判断的特定的位由res确定， res中只有一位为1，其他位均为0，由FindFirstBit1函数返回， 而data中要判断的位便是res中这唯一的1所在的位 */  
        public static boolean IsBit1(int data,int res)  
        {  
            return ((data & res)==0) ? false:true;  
        }  
    
        public static void main(String[] args) {
            int[] a = { 1,1,2,2,3,44,55,55,66,66,34,34,5,5,7,7 };
            FindNumsAppearOnce(a);
        }
    }

运行结果为：  
3and44

> **转载请标明出处，原文地址：[https://blog.csdn.net/weixin\_41835916][https_blog.csdn.net_weixin_41835916]  
> 如果觉得本文对您有帮助，请点击顶支持一下，您的支持是我写作最大的动力，谢谢。  
> 。**

[https_blog.csdn.net_weixin_41835916]: https://blog.csdn.net/weixin_41835916