《剑指offer》编程题java实现（十一）：数组中只出现一次的两个数字

问题描述

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

思路

• 使用异或：相同为0，不同为1；任何一个数字异或它本身都等于0；任何数字与0异或都为本身；
• 把原数组分成两个子数组，是的每个子数组包含一个只出现一次的数字，而其他数字都成对出现两次，这样分别异或，两个数组最后剩下的值即为两个只出现一次的数字。
• 如何分组：将数组元素逐次异或，因为有两个值不一样，所以结果肯定不为0，那么结果数组中至少有一位为1，那么找到该位，以该位是否为1分成两组，相同的元素分成了一组，因为这两个数字不一样，那么他们肯定不在同一组。
• 复杂度为O(N)
• 里面多次用到了位运算的知识，知识忘了需要再补充一下

代码实现

package com.nowcoder;

public class FindNumsAppearOnce {

    /**
     * //num1,num2分别为长度为1的数组。传出参数 //将num1[0],num2[0]设置为返回结果
     * 注：本方法的有效性验证其实不足，虽然通过了牛客的AC测试，但是对于输入的数组验证还是不足，
     * 比如有三个只有一次的数字，重复的数字重复次数为3等等，不过目前没有太好的办法，先这样
     */
     public void FindNumsAppearOnce11(int [] array,int num1[] , int num2[]) {
             if (array==null) {
                return;
            }
             //初始化两个数组
             num1[0]=0;
             num2[0]=0;
            int nLength=array.length;
            int resultExclusive=0;
            //先对整个数组进行异或
            for(int i=0;i<nLength;i++) {
                resultExclusive^=array[i];
            }
            //找到第几位为1，如果target为0，则表示，该数组不符合要求
            int bitTarget=FindFirstBit1(resultExclusive);
            if (bitTarget>32) 
                return;
            for(int i=0;i<nLength;i++) {
                if (IsBit1(array[i],bitTarget)) {
                    num1[0]^=array[i];
                }else {
                    num2[0]^=array[i];
                }
            }
        }

     //该函数从最右边开始，找到第一个为1的位,里面涉及到了位运算，num>>1,表示右移1,依次右移，并且与1进行与运算再进行判断
    private int FindFirstBit1(int resultExclusive) {
        int index=1;
        //此处要进行有效性验证，验证是否全为0的情况
        while((resultExclusive&1)==0&&index<=32)
        {
            resultExclusive=resultExclusive>>1;
            index++;
        }
        //如果不存在，则返回33
        return index;
    }

    //判断指定位是否为1，进行分组，
    private boolean IsBit1(int resultExclusive,int bitTarget) {
        boolean isBit11=false;
        resultExclusive=resultExclusive>>(bitTarget-1);
        if ((resultExclusive&1)==1) {
            isBit11=true;
        }
        return isBit11;
    }
    public static void main(String[] args) {
        int [] arr= {1,1,2,3,3,4,5,5,6,6};
        int [] num1=new int[1];
        int [] num2=new int[1];
        FindNumsAppearOnce findNumsAppearOnce=new FindNumsAppearOnce();
        findNumsAppearOnce.FindNumsAppearOnce11(arr,num1,num2);
        System.out.println(num1[0]);
        System.out.println(num2[0]);
    }
}