84 落单的数 III

原题网址：http://www.lintcode.com/zh-cn/problem/single-number-iii/#

给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。

您在真实的面试中是否遇到过这个题？

Yes

样例

给出 [1,2,2,3,4,4,5,3]，返回 1和5

挑战

O(n)时间复杂度，O(1)的额外空间复杂度

标签

思路：

最开始用暴力循环来破解，设置一个与数组长度相同的vector<bool>，二重循环遍历数组找到不重复的两个数，标记为false，再遍历vector<bool>将对应不重复元素压入结果数组中，运行时显示超时……我就知道没这么简单。

改进算法：嗯，主要是减少时间复杂度。联想到前几个例子，可以利用起来，首先用sort排序，然后一次遍历找到第一个落单的数，将其压入结果数组中；

再将第一个落单的数再次压入输入数组中，这样形参数组A中就只剩一个落单的数了，接下来用异或找到第二个落单的数压入结果数组中，最后AC。

 1 class Solution {
 2 public:
 3     /*
 4      * @param A: An integer array
 5      * @return: An integer array
 6      */
 7     vector<int> singleNumberIII(vector<int> &A) {
 8         // write your code here
 9         vector<int> result;
10      if (A.empty())
11      {
12          return result;
13      }
14      int size=A.size();
15      sort(A.begin(),A.end());
16      for (int i=0;i<size-1;i+=2)
17      {
18          if (A[i]-A[i+1]!=0)
19          {
20              result.push_back(A[i]);
21              A.push_back(A[i]);
22              break;
23          }
24      }
25      int temp=0;
26      for (int j=0;j<(int)A.size();j++)
27      {
28          temp=temp^A[j];
29      }
30      result.push_back(temp);
31      return result;
32     }
33 };

挑战版：参考 https://blog.csdn.net/guoziqing506/article/details/52231357

我们之前已经做过两道类似的题目，分别是落单的数，落单的数 II，思路都是位运算。这道题也不例外。

不过这道题想出方法来倒还真不太容易，至少我当时没想出来，也是后来查了别人的做法，才知道的，在此，我将别人的方法用我的话再说一遍，努力让它更好理解。

当然，首先想到的就是跟之前2*n + 1个数时的情况一样（详见：落单的数），先将所有的数异或一遍，这样，我们就将数组中那两个不同的数异或到了一个结果中（此处不懂的话看刚才给的链接）。现在的难处在于无法将这个结果拆开，拆成我们想要的那两个不同的数。

怎么办呢？我们如果对二进制足够熟悉，就不难得出这样一个结论，这个异或的结果（为方便描述，记为Xor）的二进制位中为1的位，必然是这两个不同的数（方便起见，记为first 和 second）不同的位，也就是说，first和second在这些位中一个是1，一个是0。不失一般性，我们就找Xor中第一个为1的位，将这个位数记为k.

那么，一定隐含了这样一个逻辑：在成对的2*n个数当中，一定有2x个数的第k位是1，而有2y个数的第k位是0，其中，x + y = n，所以，

换个说法，既然Xor的第k为是1，那我们不妨假设first的第k位是0，而second的第k位是1。那么，如果令x个数第k位为1的数，和second一起，与Xor异或，就能得到first，这个道理与2n + 1时是一样的。而再令first与Xor异或，就能得到second.

于是，可以按以下步骤操作：

1. 将数组中所有的数异或，得到一个结果，记为Xor

2. 查出Xor中第一个为1的位（也就是为1的最小的位），记为k

3. 查出数组中所有第k位为1的数（这里面当然包括second）与Xor异或，得到first

4. 将first与Xor异或，得到second

PS：位运算不会改变原变量的值。要改变原变量的值需要经过赋值表达式实现。

vector<int> singleNumberIII(vector<int> &A)
{
    vector<int> result;
    int temp=0;
    for (int i=0;i<(int)A.size();i++)
    {
        temp=temp^A[i];
    }
    int first=temp;
    int second=temp;

    int k=0;
    for (;k<32;k++)
    {
        if(temp>>k&1)
            break;
    }
    
    for (int j=0;j<(int)A.size();j++)
    {
        if (A[j]>>k&1)
        {
            first=first^A[j];
        }
    }
    second=second^first;   //second=temp^first;
    result.push_back(first);
    result.push_back(second);
    return result;
}

其他参考：

https://blog.csdn.net/wangyuquanliuli/article/details/46638551

https://www.cnblogs.com/libaoquan/p/7141364.html