Leetcode Hot100系列136.只出现一次的数字

• 其余元素均出现两次，只有一个元素出现一次，首先想到的就是使用 HashMap，统计每个元素出现的次数，然后找到value值为1的key值即可。
• 但题目要求不使用额外空间来实现，所以Java集合都不能使用，这时就要想到 异或运算
• 二进制按位XOR运算：java中的位运算符号^是将两个数按二进制的形式进行异或运算，然后再转换为十进制。异或运算有如下性质：
  • 一个数和0做XOR运算等于本身：a⊕0 = a
  • 一个数和其本身做XOR运算等于0：a⊕a = 0
  • XOR运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
• 这道题最重要的条件是 其余每个元素均出现两次 ，这代表着这些元素异或的结果为0。那么只出现一次的元素就是最后所有元素异或的结果。

class Solution {
    public int singleNumber(int[] nums) {
    	int number = 0;
    	for (int num : nums) {
    		number ^= num;
    	}
    	return number;
    }
}

• 这道题目也是可以使用按位异或来做，要分组。
  • 首先明确所有的数异或就等于这两个出现一次的数进行异或。
  • 其次，这两个数不同 → rightarrow →异或的结果一定不为0 → rightarrow →在某一个二进制位 x x x上二者一定不同 → rightarrow →只有二进制位 x x x上为1的数 X X X与数组中所有的数进行&操作的运算 → rightarrow →结果分为0和不为0的两组 → rightarrow →这两个不同的数一定在不同的组 → rightarrow →并且出现两次的数中相同的数与 x x x进行&操作的结果相同会被分到同一组 → rightarrow →转化为2组的一个问题。

class Solution {
    public int[] singleNumbers(int[] nums) {
    	int[] res = new int[2];
    	int number = 0;
    	for (int num : nums) {
    		number ^= num;
    	}
    	int flag = 1;
    	while ((number & flag) == 0) {
    		flag <<= 1;
    	}
    	for (int num : nums) {
    		if((num & flag) == 0) {
    			res[0] ^= num;
    		} else {
    			res[1] ^= num;
    		}
    	}
    	return res;
    }
}

说明：

1. 位运算符的计算看菜鸟教程。<<代表数字按位运算全部往左移动几位，相当于是2的几次方倍，&的运算符是按位运算都为1时才能为1否则为0。
2. 下面这段代码的意思就是找到number 中按位运算其中从右往左数第一个为1的某一位。即为最后的flag。

int flag = 1;
while ((number & flag) == 0) {
    flag <<= 1;
}

• 这道题已经提示的很明显了，使用异或操作就能得出汉明距离。关键问题在于如何求出异或操作后按位运算中1的个数。
• 对于 非负数 而言：
  • 左移>>：低位补0，可以直至最后左移到全为0；
  • 右移<<：高位补0，直接舍弃低位，可以直至最后右移全为0。
• 此题可以让最后结果不停与1进行&的操作，然后让该结果按位不停右移，直至该结果为0即可。

class Solution {
    public int hammingDistance(int x, int y) {
        int num = x ^ y;
        int distance = 0;
        while (num != 0) {
            distance += num & 1;
            num >>= 1;
        }
        return distance;
    }
}

• 当题目中出现 数组中的元素重复两次时，一定要考虑使用 异或XOR