文章目录

1. 1. Single Number

Single Number

---

给定一个数组，里面的数只有一个数的数量是1个，其他的数都是2个，问题是求出这个数量是单个的数。

方法1：我们可以用hash来存数组中的数出现的次数。这样的时间复杂度是O(n)，空间复杂度也是O(n)。

那么有没有方法是不需要额外的空间的呢？

我们可以利用异或操作(^)，相同的数异或那么会返回0。因为数组中的数只有一个是不同的，那么对所有数都进行异或的话，会将全部相同的数对都变成0。最终只会留下那个数量是单个的数。