只出现一次的数字III

来源Leetcode第260只出现一次的数字III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例 :

1 2	输入: [1,2,1,3,2,5] 输出: [3,5]

Hash

建立一个值到频率的映射关系的哈希表，返回频率为 1 的数字。

public int addDigits(int num) {
    if(num < 10)
        return num;
    LinkedList<Integer> list = new LinkedList<>();
    //int sum = 0;
    while(true){
        while(num > 0) {
            list.add(num % 10);
            num = num / 10;
        }
        while(!list.isEmpty()){
            num += list.removeFirst();
        }
        if(num < 10)
            break;
    }
    return num;
}

位运算

来源官方题解

在做这题时没有注意到题目给出了信息其余所有元素均出现两次，这样就好说了。

首先计算 bitmask ^= x，则 bitmask 不会保留出现两次数字的值，因为相同数字的异或值为 0。但是 bitmask 会保留只出现一次的两个数字（x 和 y）之间的差异。我们通过 bitmask & (-bitmask) 保留 bitmask 最右边的 1，这个 1 要么来自 x，要么来自 y。当我们找到了 x，那么 y = bitmask^x。

另外一个解释：

1.对所有数字异或,一样的数字抵消,出现一次的两个数字异或运算后必定不为0;
2.这个数字和相反数做与运算得到一个二进制位最右边一位为1的数字;
3.mask和数组的每个数字做与运算,等于0的分为一组,等于mask的分为一组,同时也将两个不一样的数字分开;
4.完结。

public int addDigits(int num) {
    if(num < 10)
        return num;
    LinkedList<Integer> list = new LinkedList<>();
    //int sum = 0;
    while(true){
        while(num > 0) {
            list.add(num % 10);
            num = num / 10;
        }
        while(!list.isEmpty()){
            num += list.removeFirst();
        }
        if(num < 10)
            break;
    }
    return num;
}

public int[] singleNumber(int[] nums) {
    int xor = 0;
    for (int i : nums)// 一样的抵消,不一样的两个数字异或运算结果必定有一位是1
        xor ^= i;

    int mask = xor & (-xor);

    int[] ans = new int[2];
    for (int i : nums) {
        if ((i & mask) == 0)//== 0、 == mask 两种结果
            ans[0] ^= i;
        else
            ans[1] ^= i;
    }

    return ans;
}