260. 只出现一次的数字 III

题目

题解

题解一

• 直接使用 HashSet 判断

class Solution {
    public int[] singleNumber(int[] nums) {

        Set set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }
        }
        int[] res = new int[2];
        int index = 0;
        for (Integer i : set) {
            res[index++] = i;
        }
        return res;
    }
}
1

题解二

• 对数组所有元素求 异或，得到的值为那两个不同元素的 异或结果
• 明确那两个数肯定不同，所以肯定有的位数 异或后结果为 1

  • 假如第 x 位异或的结果为 1，即所有数的 x 位异或结果为 1
  • 找到 x 的最小值
• 现在数组中只有两类数：x 位为 0 的，和 x 位为 1 的，并且这两个不同的数的 x 位还不同
• 通过 & 操作，将数组氛围两类
• 最后问题拆解为 136.只出现一次的数字

class Solution {
    public int[] singleNumber(int[] nums) {

        // 两个不同数的异或值
        int tmp = 0;
        for (int num : nums) {
            tmp = tmp ^ num;
        }
        // 两个数不同，tmp 肯定不为 0，得到最后为 1 的位
        // 4  -> 100
        // -4 -> 11111111111111111111111111111100
        // 4 & -4 -> 100
        int fg = tmp & -tmp;

        // 数组里面所有数的该位要么是 0，要么是 1，且与运算之后最终结果是 1
        int res1 = 0;
        int res2 = 0;
        for (int num : nums) {
            if ((num & fg) == 0) {
                res1 = res1 ^ num;
            } else {
                res2 = res2 ^ num;
            }
        }
        return new int[]{res1, res2};
    }

}
1