现在给你一个数组，里面放了一些数字，里面都是两两成对，只有一个数字是单独的，要求找出其中只出现一次的数字。相必这道题是非常简单了，有很多解法比如说用暴力求解？比如说用位运算？甚至说用哈希数组统计？
相信大家都有很多方法去解决这个简单的问题，在本文中我收录了三道比较简单的关于“只出现一次的数字”话题的三道题目，我均用位运算的方法去解决，有需要借鉴即可。
1.只出现一次的数字1
题目链接：LINK
class Solution { public: int singleNumber(vector<int>& nums) { // 异或思路 /* * 原理： * 两个相同的数字相异或为0 * 0异或上任何数字都为任何数字 * 异或支持交换律 */ int ret = 0; for(auto& n: nums) { ret^=n; } return ret; } };
上面这道题非常简单，我不再多说。
接下来上一点点难度。
2.只出现一次的数字2
题目链接：LINK
看到这个题目是不是感觉直接位运算不行了？直接位运算的确不行，但是我们到比特位的视角仍然是可以滴。
这个题目之前是写过博客的，详细情况去直接看我写的那个博客文章吧：链接是LINK
class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; // 以比特位为单位，对每个数据进行遍历 for(int i = 0; i < 32; i++) { int count = 0; // 统计所有数字第i位有多少个1 for(auto& n: nums) { if(((n >> i) & 1) == 1) { count++; } } // 如果这个1的个数模3刚好剩下一个，那么我们的ret也是要有1的。 if(count % 3 == 1) { ret = (ret | (1 << i)); } } return ret; } };
好，倘若你可以独立完成这道题，当然是第一次做的话，说明你的思维贼好使。我们继续来看下面这道题：
3.只出现一次的数字3
题目链接：LINK
这个思路就是把所有数字异或起来，最后得到一个数，这个数其实等价于恰好出现一次的那两个数相异或的结果。我们找到这个数有1的地方，说明两个要返回的数字对应位置的比特位是不一样的。然后我们再根据这个不一样的比特位让所有数分成两组，对每组单独异或就可得到两个要求的数字。
注：上图来源于力扣官方题解。
按照思路，我们可以写出下面代码：
class Solution { public: vector<int> singleNumber(vector<int>& nums) { // 找出两个不同数的最右的差异为1 int t_ret = 0; for(auto& n: nums) { t_ret^=n; } int l = t_ret & (-t_ret); // 根据差异我们将所有数字归为两类，一类是一位有1的，另一类是没1的。 int ret1 = 0; int ret2 = 0; for(int& n : nums) { if(n & l) { ret1 ^= n; } else { ret2 ^= n; } } return {ret1, ret2}; } };
然后…
原因在于：
所以我们在分组之气做一个判断就行了：
class Solution { public: vector<int> singleNumber(vector<int>& nums) { // 找出两个不同数的最右的差异为1 int t_ret = 0; for(auto& n: nums) { t_ret^=n; } // 特殊情况：溢出问题，因为INT_MAX所表示的数字比INT_MIN少一个！此时取符号会溢出 int l = (t_ret == INT_MIN ? t_ret : t_ret & (-t_ret)); // 根据差异我们将所有数字归为两类，一类是一位有1的，另一类是没1的。 int ret1 = 0; int ret2 = 0; for(int& n : nums) { if(n & l) { ret1 ^= n; } else { ret2 ^= n; } } return {ret1, ret2}; } };
4.总结
在上面三道题中我们都用了位运算的思路去做，第一道是比较常规的，第二道是需要理解比特位、位运算才可以想得到，第三道感觉是有点难度的，我就没想到…看的题解~
EOF
