题目描述

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

示例 1：

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这一题明确要求说是O(n)的时间 和 O(1)的空间
就限制了很多可能的解法
因为如果不加限制的话，我可能就会想用一个辅助的结构来保存出现过的数字，出现了第二次就去除，遍历完成后剩下的两个数字就是这个单独的数
但是这样的话空间复杂度会不符合要求
当然，排序一遍再看的话，确实也会导致超时，除非你能O(n)级别的排序完成

看了别人的题解：妙哇！！！
异或，两个相同数字的异或的结果是0，0和一个数字的异或结果是该数字
4 ^ 1 ^ 4 ^ 6 => 1 ^ 6
但是还存在一个问题，就是有两个单独的数字，所以需要分别去找出这两个数字
就需要分组异或

怎么分组，想将两个不同的数字分开，同时相同的数字尽量在同一组，不是尽量是必须

记这两个只出现了一次的数字为 a 和 b，那么所有数字异或的结果就等于 a 和 b 异或的结果，我们记为 x。如果我们把 x写成二进制的形式
我们只要找一个为1的位来区分数组，按照第 i 位给原来的序列分组，如果该位为 0 就分到第一组，否则就分到第二组，这样就能满足以上两个条件：

  • 首先，两个相同的数字的对应位都是相同的，所以一个被分到了某一组，另一个必然被分到这一组，所以满足了条件 2。
  • 这个方法在 x_i =1 的时候 a 和 b 不被分在同一组，因为 x_i =1 表示 a_i 和 b_i 不等

代码实现：

  1. class Solution { 
  2. public:
  3.     vector<int> singleNumbers(vector<int>& nums) {
  4.         int ret = 0;
  5.         for (int n : nums)
  6.             ret ^= n;
  7.         int div = 1;
  8.         while ((div & ret) == 0)
  9.             div <<= 1;
  10.         int a = 0, b = 0;
  11.         for (int n : nums)
  12.             if (div & n)
  13.                 a ^= n;
  14.             else
  15.                 b ^= n;
  16.         return vector<int>{a, b};
  17.     }
  18. };