Leetcode 136.只出现一次的数字

题目描述：

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

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

示例 1:

1
2

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

示例 2:

1
2

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

链接：

https://leetcode-cn.com/problems/single-number

题目分析

  很经典的一道题，以前已经做过，知道这道题的骚套路，这里需要用到的是位运算中的异或运算。首先异或运算有以下几个特点

• 一个数与 0 异或还是它本身，也即 $0\oplus a = a$。
• 一个数与本身异或的结果为 0，也即 $a\oplus a = 0$。
• 异或运算满足交换律与结合律，也即 $a\oplus b = b\oplus a$，$a\oplus(b\oplus c)=(a\oplus b)\oplus c$。

  在这个题目中，有一个数字出现了一次，其他数字都出现了两次。如果我们将 0 与所有的数字异或一次，则出现了两次的数字得到的结果会变为 0，最后留下的就是 0 与出现了一次的那个数字的异或结果，也即留下的就是只出现了一次的那个数字。

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(const int num : nums){
            result ^= num;
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为数组的大小。我们遍历了一次数组。
  空间复杂度：$O(1)$。我们只需要使用一个变量记录异或结果。

  如果没有这么骚的解法，其实也有很多其他需要额外空间但仍然是线性时间复杂度的解法，比如维护一个哈希表记录每个数字出现的次数；或者是将未在哈希表中的数字加入，而已经存在的数字删除，最后留下的也是那个只出现了一次的数字；或者利用元素和，分别记录出现的数字以及数组的数字和，这个和再加上那个只出现过一次的数字得到的结果应该是所有出现过的数字和的两倍。