📃 题目描述

题目链接：

• 剑指 Offer II 004. 只出现一次的数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 137. 只出现一次的数字 II - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,100]
输出：100

🔔 解题思路

首先需要了解下左移右移的知识，可以看这篇博客：简单理解二进制的左移和右移（通俗易懂）_一只青木呀的博客-CSDN博客_二进制左移 (opens new window)

二进制左移几位就是后面加几个 0，前面去掉几位（左移一位相当于乘 2）

右移几位就是在二进制的前面加几位（正数加 0，负数加 1），后面去掉几位（右移一位相当于除2）

在这个题目中只有一个数字出现了一次，其他数字出现了3次。相同的3个数字异或的结果是数字本身，但是将数组中所有数字进行异或运算并不能消除出现3次的数字。因此，需要想其他办法。

一个整数是由 32 个 0 或 1 组成的。我们可以将数组中所有数字的同一位置的数位相加。如果将出现 3 次的数字单独拿出来，那么这些出现了 3 次的数字的任意第 i 个数位之和都能被 3 整除(二进制中每个数位只有 0 和 1 的可能嘛)。

因此

• 如果数组中所有数字的第 i 个数位相加之和能被 3 整除，那么只出现一次的数字的第 i 个数位一定是 0；
• 如果数组中所有数字的第 i 个数位相加之和被 3 除余 1，那么只出现一次的数字的第 i 个数位一定是 1

这样只出现一次的任意第 i 个数位可以由数组中所有数字的第 i 个数位之和推算出来

class Solution {
    public int singleNumber(int[] nums) {
        int[] bitNums = new int[32];
        for (int num : nums) {
            // 将 num 看成二进制进行处理
            for (int i = 0; i < 32; i ++) {
                // 与 1 相 & 可以保存最后一位数，前面其他数位全部清 0
                bitNums[i] += (num >> (31 - i)) & 1;
            }
        }
    
        int res = 0;
        for (int bitNum : bitNums) {
            res = (res << 1) + bitNum % 3;
        }

        return res;
    }
}

代码 (num >> (31 - i)) & 1用来得到整数 num 的二进制形式中从左数起第 i 个数位(从 0 开始计数)。

整数 num 先被右移 31-i 位，原来从左数起第 i 个数位右移之后位于最右边。

接下来与 1 做位与运算。整数 1 除了最右边一位是1，其余数位都是0，它与任何一个数字做位与运算的结果都是保留数字的最右边一位，其他数位都被清零。

如果整数 num 从左数起第 i 个数位是1，那么 (num >> (31 - i)) & 1 的最终结果就是 1；否则最终结果为 0。

举个例子，求 8 位二进制整数01101100从左数起的第 2 个（从 0 开始计数）数位。我们先将 01101100 右移5位（7-2=5）得到00000011，再将它和00000001做位与运算，结果为00000001，即1。8 位二进制整数 01101100 从左边数起的第 2 个数位的确是1。

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：