解决|由浅入深，解决三道[只出现一次的数]！动图|运算符|题目|数组

文章插图
作者 | 袁厨
头图 | CSDN下载自视觉中国
今天我们来做几道非常经典的题目，第一道题目我们会用多种方法解答，虽然这是一道简单题目，但是我们学会了这几种解题方法，完全可以轻松应对后面两道中等题目。废话不多说，我们来看题目吧。
为保证严谨性，文章中的所有代码均经过测试，大家可以放心食用
题目来源：leetcode 136只出现一次的数(简单)，137只出现一次的数Ⅱ(中等)260只出现一次的数Ⅲ(中等)
只出现一次的数
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例 1:
输入: [2,2,1]输出: 1
示例 2:
输入: [4,1,2,1,2]输出: 4
这个题目非常容易理解，就是让我们找出那个只出现一次的数字，那么下面我们来看一下这几种解题方法吧
HashMap
用 HashMap 的这个方法是很容易实现的，题目要求不是让我们求次数嘛，那我们直接遍历数组将每个数字和其出现的次数存到哈希表里就可以了，然后我们再从哈希表里找出出现一次的那个数返回即可。

文章插图
题目代码：

文章插图
排序搜索法
这个方法也是特别容易想到的，我们首先对数组进行排序，然后遍历数组，因为数组中其他数字都出现两次，只有目标值出现一次，所以则让我们的指针每次跳两步，当发现当前值和前一位不一样的情况时，返回前一位即可，当然我们需要考虑这种情况，当我们的目标值出现在数组最后一位的情况，所以当数组遍历结束后没有返回值，则我们需要返回数组最后一位，下面我们看一下动图解析。

文章插图

文章插图
HashSet
这个方法也是比较容易实现的，我们利用 HashSet 来完成。HashSet 在我们刷题时出现频率是特别高的,它是基于HashMap 来实现的，是一个不允许有重复元素的集合。那么在这个题解中，它起到什么作用呢？
解题思路如下，我们依次遍历元素并与 HashSet内的元素进行比较，如果 HashSet 内没有该元素（说明该元素第一次出现）则存入，若是HashSet已经存在该元素(第二次出现)，则将其从 HashSet中去除，并继续遍历下一个元素。最后 HashSet 内剩下的则为我们的目标数。思路和我们之前说过的括号匹配问题类似，我们一起来看一下动图解析吧。

文章插图

文章插图
栈
该方法也很容易想到，我们首先将其排序，然后遍历数组，如果栈为空则将当前元素压入栈，如果栈不为空，若当前元素和栈顶元素相同则出栈，继续遍历下一元素，如果当前元素和栈顶元素不同的话，则说明栈顶元素是只出现一次的元素，我们将其返回即可。这个题目也可以使用队列做，思路一致，我们就不在这里说明啦。下面我们看下动图解析。

文章插图

文章插图
求和法
这个方法也比较简单，也是借助咱们的 HashSet 具体思路如下，我们通过 HashSet 保存数组内的元素，然后进行求和（setsum），那么得到的这个和则为去除掉重复元素的和，我们也可以得到所有元素和（numsum）。因为我们其他元素都出现两次，仅有一个元素出现一次，那我们通过 setsum * 2 - numsum 得到的元素则为出现一次的数。

文章插图
求和解法
上面我们的 SetSum* 2 - NumSum = z 也就是我们所求的值，是不是感觉很简单呀。
题目代码：

文章插图
位运算
这个方法主要是借助咱们的位运算符 ^ 按位异或，我们先来了解一下这个位运算符。
按位异或(XOR)运算符“^”是双目运算符。其功能是参与运算的两数各对应的二进位相异或，当两数对应的二进位相异时，结果为1。相同时为0。
任何数和0异或，仍为本身：a⊕0 = a
任何数和本身异或，为0：a⊕a = 0
异或运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b