图解LeetCode——剑指 Offer 56 - II. 数组中数字出现的次数 II

一、题目

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

二、示例

2.1> 示例 1：

【输入】nums = [3,4,3,3]

【输出】4

2.2> 示例 2：

【输入】nums = [9,1,7,9,7,9,7]

【输出】1

限制：

• 1 <= nums.length <= 10000
• 1 <= nums[i] < 2^31

三、解题思路

根据题目描述，数组中只有1个数字只出现一次，而其他的数字均出现了三次。那么如果说我们可以将每一位的二进制进行相加并且与3取余的话，重复3次的那些位都会是0；而剩下的某些位上的1，就属于这个唯一出现过一次的数字了。下面以数字26出现了3次为例，请见下图所示：

上面的解题思路中，出现了一个难处理的问题——二进制只有0和1，没法表示3，怎么办呢？针对这个问题，我们可以采用两个数来表示，即：高位hi和低位lo。因为按位计算是针对32位中每一位的相加计算，所以为了便于解释，我们只关注某一位的计算。

【针对十进制的0】，我们用00表示（hi=0，lo=0）；

【针对十进制的1】，我们用01表示（hi=0，lo=1）；

【针对十进制的2】，我们用10表示（hi=1，lo=0）；

那么如果一直执行加1并与3取余操作的话，变化就是00——>01——>10——>00——>…… 依次循环变化。那么在这个变化的过程中，我们可以归为两大类：

【第一类】当发现某一位是0的时候，那么不进行变化；

【第二类】当发现某一位是1的时候，那么进行变化；变化方式，如下图所示：

根据上面的图示，我们可以知道，针对nums数组中的每个数都执行如下操作，就可以获得最终每一位计算后的值：

lo = lo ^ num & ~hi;

hi = hi ^ num & ~lo;

而由于出现3次的数字的每一位肯定都是0，而只有出现了一次的数才不为0，而由于题目规定了这个数只出现了一次，那么我们只需要关注lo即可，即：将lo返回就是只出现了一次的那个数。

四、代码实现

class Solution {
    public int singleNumber(int[] nums) {
        int lo = 0, hi = 0;
        for(int num : nums){
            lo = lo ^ num & ~hi;
            hi = hi ^ num & ~lo;
        }
        return lo;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」