剑指 Offer 56 - I. 数组中数字出现的次数

剑指 Offer 56 - I. 数组中数字出现的次数

难度：$middle$

---

题目描述

一个整型数组 $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.length<=10000$

---

算法

(位运算)

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

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

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

如果我们可以把所有数字分成两组，使得：

两个只出现一次的数字在不同的组中；

相同的数字会被分到相同的组中。

那么对两个组分别进行异或操作，即可得到答案的两个数字。这是解决这个问题的关键。

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

记这两个只出现了一次的数字为 a 和 b，那么所有数字异或的结果就等于 a 和 b 异或的结果，我们记为 x。如果我们把 x 写成二进制的形式 $x_k{x}_{k-1}...x_2{x}_1$，其中 $x_i\in 0,1$，我们考虑一下 $x_i$ = 0 和 $x_i$ = 1 的含义是什么？它意味着如果我们把 a 和 b 写成二进制的形式，​$a_i$ 和 $b_i$ 的关系 $x_i$ =1 表示 $a_i$ 和 $b_i$ 不等，$x_i$ =0 表示 $a_i$ 和 $b_i$ ​ 相等。假如我们任选一个不为 0 的 ​ $x_i$ ，按照第 i 位给原来的序列分组，如果该位为 0 就分到第一组，否则就分到第二组，这样就能满足以上两个条件，为什么呢？

首先，两个相同的数字的对应位都是相同的，所以一个被分到了某一组，另一个必然被分到这一组，所以满足了条件 2。

这个方法在 $x_i$ =1 的时候 a 和 b 不被分在同一组，因为 $x_i$ =1 表示 $a_i$ 和 $b_i$ 不等，根据这个方法的定义「如果该位为 0 就分到第一组，否则就分到第二组」可以知道它们被分进了两组，所以满足了条件 1。

在实际操作的过程中，我们拿到序列的异或和 x 之后，对于这个「位」是可以任取的，只要它满足 $x_i$ = 1。但是为了方便，这里的代码选取的是「不为 0 的最低位」，当然你也可以选择其他不为 0 的位置。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度。

• 空间复杂度 : $O(1)$

C++ 代码

class Solution {
public:vector<int> singleNumbers(vector<int>& nums) {int ret = 0;// a or b resultfor (auto num : nums) {ret ^= num;}// search 1int 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};}
};

---