原题传送门 ->剑指 Offer 14- I. 剪绳子

描述:

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

2 <= nums.length <= 10000

思路：

先想这么一个问题：
如果数组有一个元素出现了奇数次，其他元素都出现了偶数次，如何把这个出现奇数次的元素找出来？

异或运算很容易解决。
只需把所有的都异或一下就OK了。
3^3^4^4^5 = 5

但是对于本题，这还不够。
3^3^4^4^5^6 = 5^6 =^= = 3
仅凭答案3没办法把5和6分离出来。

答案是分组。
必须想办法使：

  • 5和6分到不同的组中
  • 相同数字分到相同组中。

这里的策略是: 前面异或运算的结果是
那么，这个二进制数中的1一定是5和6异或得来的。
5和6的第一位和第二位一定是不同的。
我们可以用或者作为mask，与mask异或值为0的分在一组，不为0的分在另一组。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int mark = nums[0];
        for(int i = 1; i < nums.size(); ++i){
            mark ^= nums[i];
        }
        int mask = 1;
        while(!(mask&mark))mask = (mask << 1);//细节2
        int ans1 = 0, ans2 = 0;//细节1
        for(int i = 0; i < nums.size(); ++i){
            if(nums[i]&mask)ans1 ^= nums[i];
            else ans2 ^= nums[i];
            }
        vector<int> ans;
        ans.push_back(ans1);
        ans.push_back(ans2);
        return ans;
    }
};

另外有两个小细节：
1、异或的初始值应设为0
2、可不可以直接把mark当成mask？答案是不行。