只出现一次的数字

试题来源：力扣（英文），力扣（中文），geeksforgeeks

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

Input:nums = {1, 1, 2, 5, 5}
Output: 2

Input:nums = {2, 2, 5, 5, 20, 30, 30}
Output: 20

问题分析：

异或运算 具有下面几个规律。

a ^ a = 0 （自己和自己异或结果为 0 ）
a ^ 0 = a （ 0 和任何数字异或结果还是原来的数字）  
0 ^ a = a  
a ^ b ^ c = a ^ c ^ b （异或运算具有交换律）

题中说了只有一个数字出现一次，其他数字都出现两次，又由于异或运算具有交换律，我们只需要把数组中的所有数字都异或一遍即可。

public int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums)// 把数组中的所有数字都异或一遍即可。
        res ^= num;
    return res;
}

进阶1：

试题来源：geeksforgeeks

假如只有一个数字出现奇数次，其他所有数字都出现偶数次，找出只出现奇数次的那个数字。我们依然可以使用上面的方式把所有的数字都异或一遍就是这题的答案。

进阶2：

试题来源：力扣（英文），力扣（中文）

如果只有两个元素出现了奇数次，其他所有元素都出现了偶数次，找出只出现奇数次的那个元素。

Input:nums = {1, 1, 2, 5, 5, 5}
Output: [2,5]

问题分析：

题中说的是只有两个数字出现奇数次，其他数字都出现偶数次，假设出现奇数次的两个数字分别为 a 和 b ，我们先把数组中的所有元素都异或一遍，因为出现偶数次的异或结果为 0 ，所以数组元素最终的异或结果就是 a^b ，这个结果必定不等于 0 ，因为只有相同的元素异或结果才会是 0 ，不同的元素他们的二进制位至少有一个不同，我们可以根据这个不同的位把数组分为两组，这个时候 a 和 b 肯定是在不同两组，然后这题就变成了上面的“只有一个数字出现奇数次，其他数字都出现偶数次”的题了，我们只需要对每组单独异或运算即可。

public int[] singleNumber(int[] nums) {
    int xorRes = 0;
    // 把数组中的所有元素全部都异或一遍。
    for (int num : nums)
        xorRes ^= num;
    // 只保留最右边的1，其他的都让他变为0。
    xorRes &= -xorRes;
    int[] rets = {0, 0};
    for (int num : nums) {
        // 然后再把数组分为两部分，每部分在分别异或。
        if ((num & xorRes) == 0) {
            rets[0] ^= num;
        } else {
            rets[1] ^= num;
        }
    }
    return rets;
}