题目描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

思路描述

分组异或

让我们先来考虑一个比较简单的问题：

如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？

答案很简单：全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 0，不同结果为 1。那么在计算过程中，成对出现的数字的所有位会两两抵消为 0，最终得到的结果就是那个出现了一次的数字。

那么这一方法如何扩展到找出两个出现一次的数字呢？

那么如何实现这样的分组呢？

记这两个出现一次的数字为a,b，所有数字的异或结果即是a,b异或的结果，考虑最终结果的二进制形式，当a,b在某一位相同时为0，不同时为1，则找到其中任意一个位置为1便可进行分组了，当数组中的数与该值并运算，为0一组，为1为另一组。

算法

• 先对所有数字进行一次异或，得到两个出现一次的数字的异或值。

• 在异或结果中找到任意为 1 的位。

• 根据这一位对所有的数字进行分组。

• 在每个组内进行异或操作，得到两个数字。

Java

class Solution {public int[] singleNumbers(int[] nums) {int ret = 0;for (int n: nums) {ret ^= n;}int div = 1;while ((div & ret) == 0) {div <<= 1;}int a = 0;for (int n : nums) {if ((div & n) == 0) {a ^= n;}}return new int[]{a, ret^a};}
}

提取最右边一位1的位置：

while ((div & ret) == 0) {div <<= 1;}

也可利用位运算的性质：

div = ret & (~ret + 1);

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;for (int n : nums)if (div & n)a ^= n;return vector<int> {a, ret^a};}
};

Python

class Solution:def singleNumbers(self, nums: List[int]) -> List[int]:ret = functools.reduce(lambda x, y: x ^ y, nums)div = 1while div & ret == 0:div <<= 1a, b = 0, 0for n in nums:if n & div:a ^= nelse:b ^= nreturn [a, b]

对列表中数据两两依次累积执行函数操作：

reduce(lambda x, y: x ^ y, nums)

复杂度分析

• 时间复杂度：$O(n)$，我们只需要遍历数组两次。
• 空间复杂度：$O(1)$，只需要常数的空间存放若干变量。

注意：

• 以下为运算符优先级，忘了的人赶紧看一下，(div & ret)==0，这里的括号不能少，因为==的优先级大于&。

---

加油!

感谢!

努力!