# 0136. 只出现一次的数字

### 题目地址(136. 只出现一次的数字)

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

### 题目描述

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

说明：

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

示例 1:

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

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

```

### 前置知识

* [位运算](/leetcode-solution/thinkings/bit.md)

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

根据题目描述，由于加上了时间复杂度必须是 O(n)，并且空间复杂度为 O(1)的条件，因此不能用排序方法，也不能使用 map 数据结构。

我们可以利用二进制异或的性质来完成，将所有数字异或即得到唯一出现的数字。

### 关键点

1. 异或的性质 两个数字异或的结果`a^b`是将 a 和 b 的二进制每一位进行运算，得出的数字。 运算的逻辑是 如果同一位的数字相同则为 0，不同则为 1
2. 异或的规律

* 任何数和本身异或则为`0`
* 任何数和 0 异或是`本身`

1. 很多人只是记得异或的性质和规律，但是缺乏对其本质的理解，导致很难想到这种解法（我本人也没想到）
2. bit 运算

### 代码

* 语言支持：JS，C，C++，Java，Python

JavaScrip Code：

```js
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let ret = 0;
  for (let index = 0; index < nums.length; index++) {
    const element = nums[index];
    ret = ret ^ element;
  }
  return ret;
};
```

C Code：

```c
int singleNumber(int* nums, int numsSize){
    int res=0;
    for(int i=0;i<numsSize;i++)
    {
        res ^= nums[i];
    }

    return res;
}
```

C++ Code：

```
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        auto ret = 0;
        for (auto i : nums) ret ^= i;
        return ret;
    }
};

// C++ one-liner
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        return accumulate(nums.cbegin(), nums.cend(), 0, bit_xor<int>());
    }
};
```

Java Code：

```java
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int n:nums)
        {
            // 异或
            res ^= n;
        }
        return res;
    }
}
```

Python Code:

```python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        single_number = 0
        for num in nums:
            single_number ^= num
        return single_number
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$

### 延伸

有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。

和上面一样，只是这次不是一个数字，而是两个数字。还是按照上面的思路，我们进行一次全员异或操作， 得到的结果就是那两个只出现一次的不同的数字的异或结果。

我们刚才讲了异或的规律中有一个`任何数和本身异或则为0`， 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。 分组需要满足两个条件.

1. 两个独特的的数字分成不同组
2. 相同的数字分成相同组

这样每一组的数据进行异或即可得到那两个数字。

问题的关键点是我们怎么进行分组呢？

由于异或的性质是，同一位相同则为 0，不同则为 1. 我们将所有数字异或的结果一定不是 0，也就是说至少有一位是 1.

我们随便取一个， 分组的依据就来了， 就是你取的那一位是 0 分成 1 组，那一位是 1 的分成一组。 这样肯定能保证`2. 相同的数字分成相同组`, 不同的数字会被分成不同组么。 很明显当然可以， 因此我们选择是 1，也就是 说`两个独特的的数字`在那一位一定是不同的，因此两个独特元素一定会被分成不同组。

Done！

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/bao1ww.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/136.single-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.