一、题目
在一个数组 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次为例，请见下图所示：
image.png
上面的解题思路中，出现了一个难处理的问题——二进制只有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)/ ~ 「干货分享，每天更新」
网友评论