260. 只出现一次的数字 III (opens new window)

1.位运算

第一遍对数组做一次异或运算，得到两个仅出现一次数字异或的结果。tmp=x1异或x2

下一步考虑将问题“转换”成我们熟知的情况，也就是一个“数组”只有一个出现一次数字：

• 通过tmp&(-tmp)计算得到tmp的最低位1的十进制数，按照lowbit对nums数组进行分类：
  • 与运算，如果nums[i]在这个最低位上为1，那么将他放到nums1中
  • 与运算，如果nums[i]在这个最低位上为0，那么将他放到nums2中
• 通过以上分类，x1和x2肯定不会在同一个nums1或者nums2中；而对于出现两次的数字，它们肯定出现在同一个子数组中。

最后分别对nums1和nums2做一次异或运算即可。

class Solution {
    public int[] singleNumber(int[] nums) {
        int[] ans=new int[2];
        int tmp=0;
        for(int i=0;i<nums.length;i++){
            tmp=tmp^nums[i];
        }
        int lowbit=tmp&(-tmp);
        for(int i=0;i<nums.length;i++){
            int res=lowbit&nums[i];
            if(res==0) ans[0]^=nums[i];
            else ans[1]^=nums[i];
        }
        return ans;
    }
}