题目描述

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

说明：

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

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

题解思路

位运算

首先，来看个例子，比如：a^b

假设，a、b的值分别是15、2，

a 的值是15，转换成二进制为 1111，

b 的值是2，转换成二进制为 0010，

这下可以根据异或的运算规律，可以得出其结果为 1101，即13。

1 1 1 1
⊕ 0 0 1 0
————————————
1 1 0 1

继续看看，我们可以来看看⊕的运算性质：

a⊕0 = a

a⊕a = 0

a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b

继续看这道题，输入的数组一定是奇数个，

现在我假设一共有 2m+1 个元素，

其中，m对元素是成对出现的，唯一1个元素就是将被输出的结果。

接下来可以根据这个假设，列出这个表达式，

(a1⊕a2⊕⋯⊕am)⊕(a1⊕a2⊕⋯⊕am)⊕am+1

⇨ (a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(am⊕am)⊕am+1

⇨ 0⊕0⊕⋯⊕0⊕am+1

⇨ am+1

下面的代码就是采用按位异或操作符来完成的。

哈希表

成功提交后，我看了其他其他题解，大部分都是使用异或运算来完成。

但是，还有一些是使用哈希表来完成的。

对哦，为什么我不用 Hash 表呢？

~~因为我还不会 Hash 表啊hhh~~

好吧，不会归不会，但也得学学。

这里就直接小本本上记录两个使用Hash来实现的算法：

代码

使用位运算来完成。

class Solution {
       public int singleNumber(int[] nums) {
           // (a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(am⊕am)⊕am+1        // ⇨ 0⊕0⊕⋯⊕0⊕am+1=am+1        // 结合三个性质：        // 1、a⊕0 = a        // 2、a⊕a = 0        // 3、a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b        int key = 0;        for(int num : nums){
               // 比如：a^b=13            // a 的值是15，转换成二进制为1111，            // b 的值是2，转换成二进制为0010，            // 根据异或的运算规律，可以得出其结果为1101，即13            key ^= num;        }        return key;    }}