题目链接

题意

在一个数组中，除了两个数字外，其余的数字都出现了两次，找出这两个只出现了一次的数字。

题解

在这里，我们先来考虑一个稍微简单的问题。

在一个数组中，除了一个数字以外，其余数字都出现了两次，找出这个数字。

那么对于这个问题，我们可以直接对整个数组的数进行异或，那么最终的结果就是那个只出现了一次的数。

那么当有两个数a和b都只出现一次的情况，我们就自然而然地想到：如果能对这个数组进行分组，且这两个数被分到两个不同的组，且相同的两个数在同一个分组的话，那么直接分别对这两个数组进行异或就能得到要的两个结果。
那么关键问题就变成了，如何对数组进行分组才能满足要求呢？
这里利用整个数组的异或结果res，而我们知道这个res其实就是a、b异或的结果。那么res二进制表示中出现的1就刚好反应了a和b的不同。同时，对于数组中的其他元素，所以相同的两个数二进制表示同一位的值与同一个数异或的结果肯定相同。
那么，就可以利用res中出现的最低位1所表示的数对数组进行分组。

代码

  1. class Solution {
  2. public:
  3.     vector<int> singleNumbers(vector<int>& nums) {
  4.         int ret = 0;
  5.         //对数组中所有数进行异或，得到只出现过一次的两个数的异或结果
  6.         for (int n : nums) {
  7.             ret ^= n;
  8.         }
  9.         //找到这个结果的不为1的位置，用于对数组进行分组
  10.         int pos = 1;
  11.         //这里要注意与操作运算符的等级低于0，所以一定要括号
  12.         //此外，提示一下与操作运算符是要两个都为1时，结果才为1
  13.         while ((pos & ret) == 0) {
  14.             pos <<= 1;
  15.         }
  16.         int a = 0, b = 0;
  17.         for (int n : nums) {
  18.             //pos位置为1的数分为一组
  19.             if (n & pos) {
  20.                 a ^= n;
  21.             } else {
  22.             //pos位置为0的数分为一组
  23.                 b ^= n;
  24.             }
  25.         }
  26.         return vector<int>{a,b};
  28.     }
  29. };