一、题目
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
二、示例
2.1> 示例 1：
【输入】nums = [4,1,4,6]
【输出】[1,6] 或 [6,1]
2.2> 示例 2：
【输入】nums = [1,2,10,4,1,4,3,3]
【输出】[2,10] 或 [10,2]
限制：
-
-2<= nums.length <=10000
三、解题思路
根据题目描述，我们要在数组nums中寻找两个不同数字，那么要求时间复杂度是O(n)并且空间复杂度是O(1)。那么，我们可以考虑通过位操作的方式来解答这道题。
那么，首先我们可以采用异或的方式去除掉重复的数字。为什么可以这么处理呢？我们来看异或的计算方式，其实异或计算又被称作为“翻牌”操作，即：假设你手中有一张牌是“1”，那么对方出什么牌，最终的结果都是对方手持那张牌的相反牌。例如：你手持的牌是“1”，对方如果手持牌是“0”，则最终结果就是1（0的相反牌）；如果手持牌是“1”，则最终结果就是0（1的相反牌）。具体运算关系，请见下图所示：
那么通过上面对异或操作的介绍，我们可以得出一个结论，即：如果异或的两个位相同（都是0或者1），那么最终结果一定就是0。所以，我们也可以推导出，如果两个数字m和n是相同的，那么m与n执行异或操作，最终结果也一定会是0；具体如下图所示：
所以针对这个规律，我们如果将数组nums中所有的数字都执行异或操作的话，最终的结果一定就是那两个不同的数字（假设为：num1和num2）的异或值。那么到目前为止，本道题的难点就出现了，即：如果整个数组中，只有1个数字是不重复的，我们此时得出的值就是该值的。但是，这道题是两个不重复的值，我们怎么拆分这个结果呢？ 其实，我们只要能将原数组拆解成两份，然后使得num1和num2分别在这两个数组中即可，然后针对这两个数组分别执行循环异或操作，那么num1和num2自然也就被计算出来了。如下所示：
因为num1和num2本身就是不同的，所以我们只需要找到他们不相同的那一位，然后来划分两个数组并计算异或即可。好了，具体的解题思路就这样了，编码没有什么难度，只是其中的处理逻辑有一点点绕。
四、代码实现
class Solution {
public int[] singleNumbers(int[] nums) {
int x = 0, y = 1, num1 = 0, num2 = 0;
for (int num : nums)
x ^= num;
while((x & y) == 0)
y <<=1;
for (int num : nums) {
if ((num & y) == 0) num1 ^= num;
else num2 ^= num;
}
return new int[]{num2, num1};
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论