题目描述:给你一个非空整数数组nums,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
看到这个题第一想法应该是使用map记录数字及数字出现的次数,如果原数组长度为n,则map的记录条数就是 1 + (n / 2),则空间复杂度为O(n)
这个题的目的是让我们使用位运算的"^"(异或)运算。
如图所示计算的是:9 ^ 13 ^ 13
计算所得结果是 9,由此我们可以知道一个数与两个相同的数异或结果还是它本身,而 0 与 x(任何数)异或运算就是 x。
于是我们可以初始化一个变量为 0,然后遍历数组进行异或运算,就能得到最终结果
代码实现:
public int singleNumber(int[] nums) {int res = 0;for (int num : nums) {res ^= num;}return res;
}