# 数组中只出现一次的两个数字

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E4%BD%8D%E8%BF%90%E7%AE%97\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#位运算) [![](https://img.shields.io/static/v1?label=\&message=%E7%BB%8F%E5%85%B8\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#经典)

> [数组中只出现一次的两个数字\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8)

**问题简述**

```
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
```

**思路：位运算**

* 异或运算的性质：

  ```
  性质1：0^a = a
  性质2：a^a = 0
  性质3（交换律）：a^b = b^a
  性质4（结合律）：(a^b)^c = a^(b^c)
  ```
* 根据性质1 和性质2，可以构造如下算法：

  ```
  定义 all_xor(arr) := arr[0] ^ arr[1] ^ .. ^ arr[-1]
  记这两个不同的数分别为 a 和 b
  则 ab = a ^ b = all_xor(arr)  # 存在两个相同数字的都被消去
  因为 a != b，则 ab 的二进制表示中必然有一个为 1（因为 0^1=1）
  根据这个位置的 1 将 nums 分为两组，则 a 和 b 分别在这两组数字中，分别求一次 all_xor 即可；
  ```

<details>

<summary><strong>Python</strong></summary>

```python
class Solution:
    def FindNumsAppearOnce(self , arr: List[int]) -> List[int]:
        
        ab = 0  # 计算 a ^ b
        for x in arr:
            ab ^= x
            
        r = ab & (~ab + 1)  # 计算 ab 最右侧的 1
        
        a = b = 0
        for x in arr:  # 根据 r 位置是否为 1 将 arr 分为两组
            if r & x:
                a ^= x
            else:
                b ^= x
        
        return [a, b] if a < b else [b, a]
```

</details>


---

# 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://imhuay.gitbook.io/studies/algorithms/problems/2022/03/niu-ke-0075-zhong-deng-shu-zu-zhong-zhi-chu-xian-yi-ci-de-liang-ge-shu-zi.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.