8.3 第一次做，无法 AC
8.4 无法 AC
8.5 无法 AC
8.6 一次 AC

题目描述

原题链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

解题思路

K 神题解：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/

8.5 心得：

• 其它数字出现了三次，所以不能用异或！

• 统计！！！！下面第16行代码得用 += ！！！！

  class Solution {
    public int singleNumber(int[] nums) {
        // 我们知道，每个数字都只有一个二进制数
        // 则每个 int 类型就有唯一一个 32 位的二进制数
        // 我们用一个长度为 32 的数组来存储这些 int 型数字的二进制表示中出现 1 的次数
        // 这样的话，只要某个数字出现了三次，那么该数组的某位就是 3
        // 我们再对 3 取余就可以将为 3 的位给清 0
        // 这样这个数组剩下的要么是 1 要么是 0
        // 其实结果就是我们要的只出现一次的数的二进制表示形式
        // 统计出各个32位二进制数字中每一位的数量，重点是可以统计出各个数字的各个 1 
        int[] counts = new int[32];
        for(int num : nums) {
            for(int i = 0; i < 32; i++) {
                // 数组的最低位存储的是二进制中的最低位
                counts[i] += num & 1; // & 运算只能涉及到最右一位，所以下面得用无符号右移
                num >>>= 1; // 无符号右移一位
            }
        }
        // 将数组中的每一位对 3 取余后恢复到一个 int 型数字中，该数字就是我们要的答案
        int res = 0;
        for(int i = 0; i < 32; i++) {
            res <<= 1; // 每次都得先左移一位，一开始的 0 没事，反正也会被32位给限制住最后消失
            res |= counts[31 - i] % 3; // res 首先恢复的肯定是最左边的，最左边的恢复后用左移就可以恢复该数右边;那么数组肯定也要先从最高位开始恢复; res 最右一位一开始肯定是 0 ，所以只能用或运算
        }
        return res;
    }
  }