算法（4）统计出现次数为1的数

算法（4）统计出现次数为1的数 统计数组中出现次数为1的数 1、在一个数组中除了一个数只出现 1 次外，其余均出现 2 次，找到出现次数为 1 的数。

136. 只出现一次的数字

这道题比较简单，只需要利用亦或运算特性即可，即对于两个二进制位 a,b 有 a==b, a^b=0; a!=b, a^b=1，因此若两个数相同，则其亦或运算结果为 0。

Java 代码：

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i : nums) {
            res = res ^ i;
        }
        return res;
    }
}

2. 在一个数组中除了一个数只出现 1 次外，其余均出现 3 次，找到出现次数为 1 的数。

137. 只出现一次的数字 II

对于数组中所有的数，我们可以统计每一位上 1 的个数，并对 3 取余，因此若一个数出现三次，则对应位上的 1 必然是 3 的倍数，则剩余的是只出现 1 次的数字。

只考虑单独一位上的情况，该位有三种状态：0, 1, 2，因此考虑使用两个二进制位表示，分别为 two 表示高位，one 表示低位，则 two, one 有三种状态：00，01，10。
状态转换表为：

two（转换前）one（转换前）itwo（转换后）one（转换后）000000010101001011101001010100

将上表转换为位运算：
首先看 one，two=0时，one=one^i；two=1 时，one=one=0，
因此 one = one^i & ~two。
然后看two，此时使用新的one计算，则one=0时，two=two^i；one=1时，two=two=0，因此与 one 的计算相同，two = two^i & ~one。

Java 代码为：

class Solution {
    public int singleNumber(int[] nums) {
        int one = 0, two = 0;
        for (int i : nums) {
            one = one ^ i & ~two;
            two = two ^ i & ~one;
        }
        return one;
    }
}

3、在一个数组中有两个数只出现了1次，其余均出现 2 次，找到出现次数为 1 的数。

260. 只出现一次的数字 III

该题目中，出现1次的数有两个，因此按照题目 1 的方法得到的结果为两个数a, b 亦或的结果，无法分解出两个数，因此我们考虑将原数组按照一定的规则分为两组，其中 a, b 在不同的组，且同一个数必须分在同一组，这样的话，我们可以对两组数字分别使用题目 1 的方法。

分组方式可以按照某个二进制位是 0 或 1 来分组，因此我们需要找到某一位使得 a, b 该位的数字不同，由于亦或运算的特性，可以知道若将 a^b某一位为1，则 a 和 b在该位不同。

如此可以得到解决方案，首先对数组计算亦或结果，得到 a^b，找到其中某个为1的位，并将数组按照该位分组，分别计算亦或结果，得到的两个结果即为 a, b。

Java 代码：

class Solution {
    public int[] singleNumber(int[] nums) {
        int res = 0;
        for (int i : nums) {
            res = res ^ i;
        }
        // 找到最低位的1
        int x = 1;
        while ((res & x) == 0) {
            x <<= 1;
        }
        int a = 0, b = 0;
        for (int i : nums) {
            if ((i & x) == 0) {
                a = a ^ i;
            } else {
                b = b ^ i;
            }
        }
        return new int[]{a, b};
    }
}

4、长度为 n 的数组中包含 0~n之间的数但缺少其中一个，找到缺失的数。

268. 丢失的数字

亦或运算还可以用来解决缺失数字的问题，如数组 [0, 3, 1] 中缺少 2。由于只缺少一个数，因此若给该数组添加 0, 1, 2, 3，则数组变为 [0, 0, 1, 1, 2, 3, 3]，问题转换为问题1，需要寻找只出现一次的数字。

Java 代码：

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res ^= i;
        }
        for (int i : nums) {
            res ^= i;
        }
        return res;
    }
}