只出现一次的数字

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

初次分析

使用HashMap记录每个出现的值为key，value自然是次数。但是题目要求不能使用额外的空间，也就是说初步的想法使用HashMap是不可行的，既然不能使用额外的空间，那么就得另寻他法了。

继续分析

使用异或。那么何为异或？异或也就是半加算法，顾名思义就是不带进位的二进制算法。异或有以下三个特点。

• 与0异或，值不变
• 与自身异或，值为0
• 满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

我们说的异或都是基于二进制的，那么我们这个题运算的时候，他怎么计算的呢？例如[1,2,1,2,4]

• 第一轮0⊕1=1。
• 第二轮1⊕2=3。这个怎么计算的呢？

  1的二进制01，而2的二进制是10，那么01和10做异或操作，即
  值为11即为3。

• 第三轮3⊕1=2

• 第四轮2⊕2=0
• 第四轮0⊕4=4

答案

public static int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

复杂度

• 时间复杂度: O(n),只需要遍历一次数组即可实现。
• 空间复杂度: O(1),只需要常数变量来记录异或运算的结果。

总结

使用了异或，当第一次遇到一个数字时，相当于加操作，遇到第二次时相当于一个减操作，最后的结果就是我们的答案。

这个题不熟悉异或的同学可能找不到这个解题的方法。做了这么久的算法，发现很多算法题都能用到数学的方法进行计算，这样说可能不合适，算法本身就是数学的一种解题方法。还是感觉自身掌握的太少了。这个题最先想到的就是有Hash来解决，看了答案才知道异或。继续加油吧。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！