> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/wei-yun-suan/260-zhi-chu-xian-yi-ci-de-shu-zi-iii.md).

# \[260]\[中等] 只出现一次的数字 III

## 题目描述

[260. 只出现一次的数字 III](https://leetcode-cn.com/problems/single-number-iii/)

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

```
输入: [1,2,1,3,2,5]
输出: [3,5]
```

注意：

结果输出的顺序并不重要，对于上面的例子， \[5, 3] 也是正确答案。 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

## 解题思路

此题与[\[136\]\[简单\] 只出现一次的数字](/garnet/suan-fa/wei-yun-suan/136-zhi-chu-xian-yi-ci-de-shu-zi.md)有类似之处. 然而数组中会有两个只出现一次的数字(当然这两个数字不相等). 直接使用136中的解法得到是数字`a`和`b`的异或结果, 无法进一步将这两个数字从它们的异或结果中分离.

一个思路就是能不能把原始的一个数组, 分成两个数组, 而且两个单独出现的数字被分到不同的数组中, 而且同一个数字在存在在一个数组中. 这样分别对两个数组使用136中的方法, 就能分开找到这两个数字了.

分组的依据很直观地可以想到依据`a`和`b`异或的结果进行分类. 重新审视两数异或的结果, 结果中值为`1`的位, 说明两个数在此位置上的值不同, 从而找到了分组的依据. 整体步骤如下:

* 对数组中所有数字进行累计异或计算, 得到两个单独出现数`a`和`b`的异或值
* 选取异或中任意一位值为1的位置(例如最左侧的值为1的位置), 再次对数组进行循环, 计算每个数与上一步结果即`a^b`的异或, 根据选取位的结果, 将结果为0的分为1组, 结果为1的分为一组
* 再对每组分别进行累计异或, 找到这两个单独出现的数字

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

        loc = 1
        for i in range(32):
            if (res1 >> i) & 1 == 1:
                break
            loc <<= 1

        res_0, res_1 = 0, 0
        for num in nums:
            if num & loc == 0:
                res_0 ^= num
            else:
                res_1 ^= num

        return [res_0, res_1]
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://kerasnoone.gitbook.io/garnet/suan-fa/wei-yun-suan/260-zhi-chu-xian-yi-ci-de-shu-zi-iii.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.