题目及其链接如下：
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
2 <= nums <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
leetcode官方给出的参考解答及链接如下：
C++
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int ret = 0;
for (int n : nums)
ret ^= n;
int div = 1;
while ((div & ret) == 0)
div <<= 1;
int a = 0, b = 0;
for (int n : nums)
if (div & n)
a ^= n;
else
b ^= n;
return vector<int>{a, b};
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
链接：官方给出的参考解答
感想·总结
【这段为废话】作为一个小白+轻度阅读障碍者，解答的文字讲解部分，一眼看，懵B，两眼看，懵B(视频我没有看)，直接上程序，看不懂。不管，先运行一下，增强我对于这分程序的信念，运行正确，再提交，仍正确。说明这几行算法的确可行且时间复杂度是O(n)，空间复杂度是O(1)。这样还想什么其它的，就是干这几行代码。因为轻薄本上未安装任何便于程序调试的IDE，故只有在脑子里想象模拟电脑对这个程序的运行，仍懵B，，，。故，只有老老实实多看些别人的解法和博客，终于，随着一声惊叹：秒哇，实在是秒哇！想通了个中原理并自己敲了出来。
③④⑤⑥⑦⑧⑨⑩
【以下是正餐】
给代码加上注释，如下：
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
//nums中所有数做一个异或运算，结果为res。
int ret = 0;
for (int n : nums)
ret ^= n;
//找到res中为1的任意一位，这里找的是为1的最低位，结果为div。
int div = 1;
while ((div & ret) == 0)
div <<= 1;
//将nums中的所有数依次和div做与运算，依结果分成两组，分别再次做或运算得出各自组内的另类数。
int a = 0, b = 0;
for (int n : nums)
if (div & n)
a ^= n;
else
b ^= n;
return vector<int>{a, b};
}
};
要明白这段代码，关键是要明白异或运算的特点：
A ^ B ^ C ^C ^ D ^ E = A ^ B ^ D ^ E
为什么，因为
①任何数与自己异或都得0；
②0与任何数异或，都得那个数；
在这一题中，数组nums中，只有两个数出现一次，其它都出现两次。故他们的异或的叠加就相当于那两个被通缉的数的异或，即：
A ^ A ^ B ^ B ^ C ^C ^ D ^ E = D ^ E
若是（问题一）被通缉的另类般的数只有一个，则这么异或叠加一下即可得出这个数。
不过本题中要找的是两个数，要求分别找出来。
现在我们得到这两个数的异或D^E，也就是程序中的res。res中为1的位上D与E不同，为0的位上D=E。
故可以通过这个res中任意一个为1的位，用与运算，区分开来D和E。所以，将nums中的所有数与res做与运算，相同的数会得到相同的结果，而D和E会得到不同的结果。这样就达到了把这个问题转化为（问题一），则，分别做一个异或运算的叠加即可分别得到各自组的那个另类数。
最后，这个方法的巧妙之处在于巧妙地利用了异或运算的特点。可是我感觉这个特点只能用于分离出来一个数组中所有个数为奇数的数，且这样的数个数要<=2，若不满足，则需要另寻方法。若有欠琢磨之处，望指正。
网友评论