【practise】只出现一次的数字

现在给你一个数组，里面放了一些数字，里面都是两两成对，只有一个数字是单独的，要求找出其中只出现一次的数字。相必这道题是非常简单了，有很多解法比如说用暴力求解？比如说用位运算？甚至说用哈希数组统计？

相信大家都有很多方法去解决这个简单的问题，在本文中我收录了三道比较简单的关于“只出现一次的数字”话题的三道题目，我均用位运算的方法去解决，有需要借鉴即可。

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位有多少个1for(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) {// 找出两个不同数的最右的差异为1int 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) {// 找出两个不同数的最右的差异为1int 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};}
};