leetcode 链接：260. 只出现一次的数字 III

题目

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例：

  1. 输入：nums = [1,2,1,3,2,5]
  2. 输出：[3,5]
  3. 解释：[5, 3] 也是有效的答案。
输入：nums = [-1,0]
输出：[-1,0]

输入：nums = [0,1]
输出：[1,0]

解答 & 代码

解法：分组异或

  • 对所有元素进行异或，最终得到的结果 sum 就是数组中只出现一次的两个元素异或的结果
    • 以 nums = [1,2,1,3,2,5] 为例，sum = 3^5，二进制的形式表示就是 sum = 0011^0101 = 0110
    • 可以使用 sum 的二进制形式中值为 1 的位来对数组的元素进行划分，如果元素值的二进制形式该为为 1，则划到同一组，否则划到另一组。这样对于出现两次的元素，相同的这两个元素会被划到同一组；而对于只出现一次的那两个元素，会被划到两个不同的组

  • 遍历数组，分别将元素划分为两个组，分别进行异或，得到的两个结果就是只出现一次的元素

    class Solution {
public:
  vector<int> singleNumber(vector<int>& nums) {
      int size = nums.size();
      // 遍历数组，对所有元素求异或，得到结果 sum
      int sum = 0;
      for(int i = 0; i < size; ++i)
      {
          sum ^= nums[i];
      }

      // 找到 sum 的二进制形式中值为 1 的位
      int div = 1;
      while((div & sum) == 0)
          div <<= 1;

      // 将数组元素划分为两组，分别进行异或，就得到两个只出现一次的元素的值
      int num1 = 0;
      int num2 = 0;
      for(int i = 0; i < size; ++i)
      {
          if((nums[i] & div) == 0)
              num1 ^= nums[i];
          else
              num2 ^= nums[i];
      }
      return vector<int>{num1, num2};
  }
};

    执行结果： ``` 执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 99.19% 的用户 内存消耗：9.7 MB, 在所有 C++ 提交中击败了 71.67% 的用户 ```