只出现一次的数字

## 1 题目

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

**说明：**

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

**示例 1:**

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

**示例 2:**

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

## 2 问题分析

1. 该题目可以使用**异或运算**来实现。
2. 异或运算有以下三个性质：

1. **任何数和 0 做异或运算**，**结果仍然是原来的数**，即 $a \oplus 0 = a$。
   2. **任何数和其自身做异或运算**，**结果是 0**，即 $a \oplus a = 0$。
   3. **异或运算满足交换律和结合律**，即 $a \oplus b \oplus a = b \oplus a \oplus a = b \oplus (a \oplus a) = b \oplus 0 = b$。
3. **假设数组中有 $ 2m + 1 $ 个数**，**其中有 $m$ 个数各出现两次**，**一个数出现一次**，**令 $a_1$**、$a_2$、...、$a_m$**为出现两次的 $m$ 个数**，**$a_{m + 1}$ 为出现一次的数**，**根据性质 3**，**数组中的全部元素的异或运算结果总是可以写成如下形式**：

$$
(a_1 \oplus a_1) \oplus (a_2 \oplus a_2) \oplus \cdot \cdot \cdot \oplus (a_m \oplus a_m) \oplus a_{m + 1}
$$

**根据性质 2 和性质 1**，**上式可化简和计算得到如下结果**：

$$
\oplus 0 \oplus \cdot \cdot \cdot \oplus 0 \oplus a_{m + 1} = a_{m + 1}
$$

**因此**，**数组中的全部元素的异或运算结果即为数组中只出现一次的数字**。

## 3 参考代码

```java
public int singleNumber(int[] nums) {
    int ans = nums[0];
    for (int i = 1; i < nums.length; i++) {
        ans ^= nums[i];
    }
    return ans;
}
```

## 4 扩展题目

### 4.1 [数组中数字出现的次数](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof)

#### 4.1.1 问题分析

1. 该题目是[只出现一次的数字](#2-问题分析)的扩展，可以采用类似的方法来解决。
2. **针对只有一个数字出现了一次**，**其他数字都出现两次的情况**，**我们可以采用对所有数字进行异或操作**，**这样最终的结果便是只出现一次的数字**。
3. **对于有两个数字出现了一次**，**其他数字都出现两次的情况**，**我们可以把所有的数字分成两组**，**使得**：
   1. **两个只出现一次的数字在不同的组上**。
   2. **相同的数字会被分到相同的组上**。
4. **此时**，**对两个组分别进行异或操作**，**便可得到两个只出现一次的数字**，因此，**关键在于如何分组**，具体可采用如下的方法：
   1. **记这两个只出现了一次的数字为 $a$ 和 $b$**，**那么所有数字的异或结果就等于 $a$ 和 $b$ 异或的结果**，**我们记为 $x$**。
   2. **如果我们把 $x$ 写成二进制的形式 $x_kx_{k-1} \cdots x_2x_1x_0$**，**其中 $x \in \left\{0,1\right\}$**，此时，$x_i$**的值就代表 $a_i$ 和 $b_i$ 的关系**，即：

$$
      \left\{\begin{array}{l}x_i=0,\;a_i=b_i\\x_i=1,\;a_i \ne b_i\end{array}\right.
      $$
   3. **假如我们任选一个不为 0 的 $x_i$**，**按照第 $i$ 位给原来的序列分组**，**如果该位为 0 就分到第一组**，**否则就分到第二组**，**这样就能满足以上两个条件**，因为：

1. **首先**，**两个相同的数字的对应位都是相同的**，**所以一个被分到了某一组**，**另一个必然被分到这一组**，**所以满足了条件 2**。
      2. **其次**，**这个方法在 $x_i = 1$ 的时候 $a$ 和 $b$ 不被分在同一组**，**因为 $x_i = 1$ 表示 $a_i$ 和 $b_i$ 不等**，**根据这个方法的定义「如果该位为 0 就分到第一组，否则就分到第二组」可以知道他们被分进了两组**，**所以满足了条件 1**。
   4. **在实际的操作过程中**，**我们拿到序列的异或和 $x$ 之后**，**对于这个位是可以任取的**，**只要他满足 $x_i = 1$**，**但是为了方便**，**这里我们选取的是「不为 0 的最低位」**。
5. 具体的算法流程如下：
   1. **先对所有数字进行一次异或**，**得到两个出现一次的数字的异或值**。

![](https://notebook.ricear.com/media/202206/2022-06-17_1244000.7151189598650409.png)
   2. **在异或结果中找到任意为 1 的位**。

![](https://notebook.ricear.com/media/202206/2022-06-17_1244000.7409195606915164.png)
   3. **根据这一位对所有的数字进行分组**。

![](https://notebook.ricear.com/media/202206/2022-06-17_1244000.43883575248146134.png)
   4. **在每个组内进行异或操作**，**得到两个数字**。

![](https://notebook.ricear.com/media/202206/2022-06-17_1244000.07782610698793824.png)

![](https://notebook.ricear.com/media/202206/2022-06-17_1244000.14969172472009196.png)

#### 4.1.2 参考代码

```java
/**
 * 剑指 Offer 56 - I. 数组中数字出现的次数
 * @param nums  数组
 * @return  数组中两个只出现一次的数字
 */
public int[] singleNumbers(int[] nums) {
    int tmp = 0, div = 1, a = 0, b = 0;

//  1. 对数组中所有的数字进行异或，得到两个只出现一次的数字的异或
    for (int num: nums) {
        tmp ^= num;
    }

//  2. 获取两个只出现一次的数字的异或中二进制位第一个不为 0 的低位
    while ((div & tmp) == 0) {div <<= 1;}

//  3. 对数组中的数字进行分组并进行异或获取两个只出现一次的数字
    for (int num: nums) {
        if ((div & num) != 0) {a ^= num;}
        else {b ^= num;}
    }

return new int[]{a, b};
}
```

### 4.2 [数组中数字出现的次数 II](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof)

#### 4.2.1 问题分析

1. 如下图所示，考虑数字的二进制形式，**对于出现三次的数字**，**各二进制位出现的次数都是 3 的倍数**，因此，**统计所有数字的各二进制位中 1 的出现次数**，**并对 3 求余**，**结果则为只出现一次的数字**。

![Picture1.png](https://notebook.ricear.com/media/202206/2022-06-17_1244000.9936426449792627.png)
2. **各二进制位的位运算规则相同**，因此**只需考虑一位即可**，如下图所示，**对于所有数字中的某二进制位 1 的个数**，**存在 3 种状态**，**即对 3 余数为 0**、**1**、**2**：

1. 若**输入二进制位为 0**，则**状态不变**。
   2. 若**输入二进制位为 1**，则**状态按照以下顺序转换**：

$$
      0 \rightarrow 1 \rightarrow 2 \rightarrow 0 \rightarrow \cdots
      $$

![Picture2.png](https://notebook.ricear.com/media/202206/2022-06-17_1244000.01575213023832789.png)
3. **由于二进制只能表示 0**、**1**，**因此需要使用两个二进制位来表示 3 个状态**，**设此两位分别为 $two$**、$one$，**则状态转换变为**：

$$
   00 \rightarrow 01 \rightarrow 10 \rightarrow 00 \rightarrow \cdots
   $$

![Picture3.png](https://notebook.ricear.com/media/202206/2022-06-17_1244000.0067849883704458325.png)
4. 接下来，**需要通过状态转换表导出状态转换的计算公式**：

1. 首先回忆一下位运算特点，**对于任意二进制位 $x$**，有：

1. **异或运算**：$x \wedge 0 = x$，$x \wedge 1 = \sim x$。
      2. **与运算**：$x \& 0 = 0$，$x \& 1 = x$。
   2. **计算 $one$ 方法**：

1. **设当前状态为 $two \; one$**，**此时输入二进制位 $n$**，如下图所示，**通过对状态表的拆分**，**可推出 $one$ 的计算方法为**：

```java
         if (two == 0) {
           if (n == 0) {
             one = one;
           } else if (n == 1) {
             one = -one;
           }
         } else if (two == 1) {
           one = 0;
         }
         ```
      2. **引入异或运算**，**可将以上拆分简化为**：

```java
         if (two == 0) {
           one = one ^ n;
         } else if (two == 1) {
           one = 0;
         }
         ```
      3. **引入与运算**，**可继续简化为**：

$$
         one = one\; \wedge\; n\; \&\; ~two
         $$

![Picture4.png](https://notebook.ricear.com/media/202206/2022-06-17_1244000.20137094576475434.png)
   3. **计算 $two$ 方法**：

$$
      two = two\; \wedge\; n\; \&\; ~one
      $$

![Picture5.png](https://notebook.ricear.com/media/202206/2022-06-17_1244010.5028293466336148.png)
   4. **返回值**：

1. **以上是对数字的二进制中一位的分析**，**而 `int` 类型的其他 31 位具有相同的运算规则**，**因此可将以上公式直接套用在 32 位数上**。
      2. **遍历完所有数字后**，**各二进制位都处于状态 00 和状态 01**（取决于只出现一次的数字的各二进制位是 1 还是 0），**而此状态是由 $one$ 来记录的**（此两状态下 $two$ 恒为 0），**因此返回 $one$ 即可**。

#### 4.2.2 参考代码

```java
/**
 * 剑指 Offer 56 - II. 数组中数字出现的次数 II
 * @param nums  数组
 * @return  数组中只出现一次的数字
 */
public int singleNumber(int[] nums) {
    int one = 0, two = 0;
    for (int num: nums) {
        one = one ^ num & ~two;
        two = two ^ num & ~one;
    }
    return one;
}
```

## 参考文献

1. [136. 只出现一次的数字](https://leetcode-cn.com/problems/single-number)。
2. [只出现一次的数字](https://leetcode-cn.com/problems/single-number/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-solution)。
3. [剑指 Offer 56 - I. 数组中数字出现的次数](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof)。
4. [数组中数字出现的次数](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-by-leetcode)。
5. [剑指 Offer 56 - I. 数组中数字出现的次数（位运算，清晰图解）](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom)。