84 落单的数 III

 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;i1;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

转载于:https://www.cnblogs.com/Tang-tangt/p/8835211.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！