面试题40. 数组中只出现一次的数字

题目描述

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

如：[2, 4, 3, 6, 3, 2, 5, 5]，只出现一次的数字为4,6

思路：

本题的核心是使用异或运算，异或运算的核心是：不同取1，相同取0

0 ^ 1 = 1 or 1 ^ 0 = 1

0 ^ 0 = 0

1 ^ 1 = 0

对于两个相同的数字，异或得到的结果为0，两个不同的数字异或得到的结果不为0

如：

4 ^ 4 = 0

4 ^ 6 = 2

了解了异或的原理后，再来看题目。在这个数组中，除了两个数字外，其他数字均出现了两次。我们对所有元素进行异或运算，即：2 ^ 2 ^ 3 ^ 3 ^ 5 ^ 5 ^ 4 ^ 6 。那些出现两次的数字进行异或计算后，得到的结果为0。本题中，2、3、5均出现两次，因此 2 ^ 2 ^ 3 ^ 3 ^ 5 ^ 5 = 0。最后只剩下数字4和6进行异或运算，4 ^ 6 = 2（0010），2的二进制中从右起第二位为1，说明4和6在第二位上不同。根据第二位上是否为1，可以将4和6分开到两个数组中，对于那些出现了两次的数字，会被同时分到某个数组中。因此，将数组分为两个部分：[2,2,3,3,6] 和 [4,5,5]。这种分法很巧妙，既可以将4和6分开到两个数组中，又可以将出现两次的数字分到同一个数组中。

对于这两个数组，对所有数字再一次进行异或运算，得到的结果就是只出现一次的数字。

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution
    public void FindNumsAppearOnce(int[] array, int[] num1 , int[] num2) {
        if(array.length < 4) return ;

        // step1. 每个元素异或运算
        int num = findNumAppearOnce(array);

        // step2. 获取num的二进制中的第一个1出现的位置（自右向左）
        int position = getPositionOf1(num);

        // step3. 根据position位置上是否为1，将数组分为两个部分
        int[] arr1 = new int[array.length];
        int[] arr2 = new int[array.length];
        partitionBy1(array, position, arr1, arr2);

        // step4. 分别对两个部分进行异或运算
        num1[0] = findNumAppearOnce(arr1);
        num2[0] = findNumAppearOnce(arr2);
    }

    public int findNumAppearOnce(int[] array) {
        int num = array[0];
        for(int i = 1; i < array.length; i++) {
            num = num ^ array[i];
        }
        return num;
    }

    // 获取数字二进制中的第一个1出现的位置（自右向左）
    public int getPositionOf1(int n) {
        int position = 1;
        while(position <= n) {
            if((n & position) != 0) {
                break;
            }
            position = position << 1;
        }
        return position;
    }

    // 根据position位置上是否为1，将数组分为两个部分
    public void partitionBy1(int[] array, int position, 
                             int[] arr1, int[] arr2) {
        int p = 0, q = 0;
        for(int i = 0; i < array.length; i++) {
            if((array[i] & position) < position) {
                arr1[p++] = array[i];
            }else