题目
一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。
你可以假设这两个数字一定存在。
样例
输入：[1,2,3,3,4,4]
输出：[1,2]

解法：位运算

思路是将两个数字拆分到两个数组中去，这样变成了在数组中找出只出现过一次的数，直接用异或就可以做出来
拆分：

  • 记两个数分别为x, y
  • 先把所有数异或，得到sum = x^y
  • 由于这两个数不同，肯定有一个二进制位不一样
  • 找出这个二进制位k，将x, y分到两个数组中

求解：

  • 先异或所有第K位为1的，记为x
  • y = sum ^ x

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

  1. class Solution {
  2. public:
  3.     vector<int> findNumsAppearOnce(vector<int>& nums) {
  4.         int sum = 0;
  5.         for (auto x: nums) {
  6.             sum ^= x;
  7.         }
  9.         int k = 0;
  10.         while ((sum >> k & 1) == 0) k++;
  12.         int num = 0;
  13.         for (auto x: nums) {
  14.             if (x >> k & 1)
  15.                 num ^= x;
  16.         }
  18.         return vector<int>{num, sum ^ num};
  19.     }
  20. };