剑指Offer的学习笔记（C#篇）-- 数组中只出现一次的数字

题目描述

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

题目给定：num1,num2分别为长度为1的数组。传出参数；将 num1[0], num2[0] 设置为返回结果。。

一 . 题目分析

题目说的太笼统，举例分析。

例如：给定的数组是这个：int[] z = new int[8] {2,4,3,6,3,2,5,5 }; 因为2/3/5都有两个，所以输出的是num1[0]=4； num2[0]=6。。

分析步骤：

1 . 遍历数组 + 遍历内容（循环异或运算）

异或运算为二进制运算符，但是运用在这里非常合适。设置一个0，从头到尾遍历数组，相同的数都相互抵消了，最后仅剩两个不同的数的异或结果。（两个相同的数可理解成第一次异或就是乘法，第二次异或就除法）

2 . 数组分组

因为要把两个不同的数组放到两个空数组里面，所以这里还要搞一下，因为上面的步骤仅仅是求出的两个数的异或结果，所以，接下来做的就是分组。可以知道的是这两个数不相同的数的异或结果肯定不是0，因为是0的话，而知就相等了。所以，我们可以考虑一下，把这两个数异或的结果搞一搞，找出他们二进制最低位的第一个1（也就是他们最低位第一个不同的位置，因为异或不同为1，相同为0嘛）。我们设一个1，用&运算符算，原因是我们设的这个1可以是000000000.....000001，&也就是AND运算符是只有两个都是1的时候才得1，其他一切情况下都是0。当然他们&后为1也是我们的停止条件。

        int y = 1;
        while( (x & 1) == 0)
        {
            x = x >> 1;
            y = y << 1;
        }

分析一下这段代码。将x与1执行AND运算。非0的话，x的二进制就右移一位，y就左移一位（虽不参与运算，但是用在下一步，作为分组的比较条件），这样就把x的第一个二进制1找到了，（例如：二进制8，就变成了y最后就变成了100）

3 . 分组挑选

通过y将数组分成两部分。

二 . 代码实现

class Solution
{
    public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2)
    {
        // write code here
        if (array.Length < 2)
        {
            return;
        }
        // 找出两个不同数的异或结果
        int x = 0;
        foreach (int i in array)
        {
            x ^= i;
        }
        // 找出他们异或结果二进制数最右面的一个1，注意(x & 1)要括起来，注意计算顺序
        int y = 1;
        while( (x & 1) == 0)
        {
            x = x >> 1;
            y = y << 1;
        }
        // 第二次遍历找出两个不同的数
        foreach(int j in array)
        {
            if ((j & y) == 0)
            {
                num1[0] ^= j;
            }
            else
            {
                num2[0] ^= j;
            }
        }
    }
}