260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

class Solution {
    public int[] singleNumber(int[] nums) {
        int[] res = new int[2];
        int j = 0;
        Map<Integer, Integer> map = new HashMap();
        for(int i: nums) map.put(i, map.getOrDefault(i, 0) + 1);
        for(int i: nums) {
            if(map.get(i) == 1) res[j++] = i;
        }
        return res;
    }
}

1. hashmap

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for(int i: nums) xor ^= i;
        int diff = xor & (-xor);
        int[] res = new int[2];
        for(int i: nums) {
            if((i & diff) == 0) res[0] ^= i;
            else res[1] ^= i;
        }
        return res;
    }
}

2.阴间方法

diff是唯一出现一次的两个数的异或的最低位是1的位置

我们知道diff是两个数的异或，而且特殊在diff是异或为1的位置，说明这两个数和diff做&运算一定不同

那我们通过做&运算来区分两个数，再通过异或来去除重复的数