LeetCode 第260题：只出现一次的数字 III

📖 文章摘要

本文详细解析LeetCode第260题“只出现一次的数字 III”，这是一道位运算问题。文章提供了从基础哈希表到高级位运算的完整思路演进，包含C#、Python、C++三种语言实现，配有详细的位运算原理图解和性能分析。适合想要深入理解位运算技巧的算法学习者。

核心知识点： 位运算、异或操作、分组技巧
难度等级： 中等
推荐人群： 位运算学习者、算法面试准备者

题目描述

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5,3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

提示

2 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次

解题思路

方法一：哈希表

最直观的方法是使用哈希表来统计每个数字的出现次数，然后找出只出现一次的两个数字。但这种方法需要额外的 O(n) 空间，不符合题目要求的常量空间。

方法二：位运算

位运算是解决此类问题的关键。我们可以利用异或运算的性质：相同的数异或结果为0，任何数与0异或结果为其本身。

关键点

如果数组中所有元素都出现两次，只有一个元素出现一次，那么对所有元素进行异或操作，最终结果就是那个只出现一次的元素。
当有两个元素（假设为a和b）只出现一次时，对所有元素进行异或，结果为a^b。
由于a和b不同，a^b必然不为0，即至少有一位为1。
我们可以找到a^b中任意一个为1的位置，将数组中的所有元素按照该位是否为1分成两组。
这样，a和b必然被分到不同的组，而其他出现两次的元素会被分到相同的组。
对每组分别进行异或操作，结果就是a和b。

具体步骤

对数组中所有元素进行异或操作，得到结果diff = a^b。
找到diff中任意一个为1的位（通常选择最低位），记为diff &= -diff（这是获取最低位1的常用技巧）。
根据这一位是否为1，将数组分成两组。
分别对两组进行异或操作，得到的结果就是只出现一次的两个数字。

复杂度分析

时间复杂度：O(n)，其中n是数组的长度。我们需要遍历数组两次。
空间复杂度：O(1)，只使用了常量额外空间。

图解思路

算法步骤分析表

步骤	操作	状态	说明
初始状态	nums = [1,2,1,3,2,5]	待处理数组	包含两个只出现一次的数字3和5
第一步	全部异或：1^2^1^3^2^5	xorResult = 6	相同数字抵消，得到3^5=6(110)
第二步	获取最低位1：6 & (-6)	diff = 2	6的二进制110，最低位1在第2位
第三步	按第2位分组	两个子数组	第2位为0的一组，第2位为1的一组
第四步	分别异或各组	result = [3, 5]	组1得到3，组2得到5

位运算分组原理表

数字	二进制表示	第2位值	分组	组内异或结果
1	001	0	组1	1^1=0，最终^3=3
1	001	0	组1	-
3	011	1	组2	异或后得到3
2	010	1	组2	2^2=0，最终^5=5
2	010	1	组2	-
5	101	1	组2	异或后得到5

代码实现

C# 实现

public class Solution {
    public int[] SingleNumber(int[] nums) {
        // 第一步：对所有元素进行异或操作，得到两个不同数字的异或结果
        int xorResult = 0;
        foreach (int num in nums) {
            xorResult ^= num;
        }
        
        // 第二步：找到xorResult中最低位的1
        // 使用 x & (-x) 技巧获取最低位的1
        int diff = xorResult & (-xorResult);
        
        // 第三步：根据该位将数组分成两组，并分别进行异或
        int[] result = new int[2];
        foreach (int num in nums) {
            if ((num & diff) == 0) {
                // 该位为0的分到第一组
                result[0] ^= num;
            } else {
                // 该位为1的分到第二组
                result[1] ^= num;
            }
        }
        
        return result;
    }
}

Python 实现

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # 第一步：对所有元素进行异或操作
        xor_result = 0
        for num in nums:
            xor_result ^= num
        
        # 第二步：找到xor_result中最低位的1
        # 在Python中处理负数的位运算需要特别注意
        diff = xor_result & (-xor_result)
        
        # 第三步：根据该位将数组分成两组，并分别进行异或
        result = [0, 0]
        for num in nums:
            if num & diff == 0:
                # 该位为0的分到第一组
                result[0] ^= num
            else:
                # 该位为1的分到第二组
                result[1] ^= num
        
        return result

C++ 实现

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // 第一步：对所有元素进行异或操作
        int xorResult = 0;
        for (int num : nums) {
            xorResult ^= num;
        }
        
        // 第二步：找到xorResult中最低位的1
        int diff = xorResult & (-xorResult);
        
        // 第三步：根据该位将数组分成两组，并分别进行异或
        vector<int> result(2, 0);
        for (int num : nums) {
            if ((num & diff) == 0) {
                // 该位为0的分到第一组
                result[0] ^= num;
            } else {
                // 该位为1的分到第二组
                result[1] ^= num;
            }
        }
        
        return result;
    }
};

执行结果

C# 实现

执行用时：152 ms
内存消耗：44.1 MB

Python 实现

执行用时：56 ms
内存消耗：17.2 MB

C++ 实现

执行用时：8 ms
内存消耗：10.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	152 ms	44.1 MB	代码结构清晰，但性能较差
Python	56 ms	17.2 MB	实现简洁，性能适中
C++	8 ms	10.2 MB	性能最佳，内存占用最小

代码亮点

🎯 巧妙利用异或运算的性质，相同数字异或为0的特点
💡 使用 diff = xorResult & (-xorResult) 快速找到最低位的1
🔍 通过位运算分组，将问题转化为两个单独的“只出现一次的数字”问题
🎨 代码简洁高效，满足线性时间复杂度和常量空间复杂度要求

常见错误分析

🚫 使用哈希表统计频次，违反了常量空间复杂度的要求
🚫 错误理解异或运算性质，导致分组逻辑错误
🚫 在寻找最低位1时使用循环遍历，而非位运算技巧，降低效率
🚫 忽略负数在不同语言中的位运算处理差异

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
哈希表	O(n)	O(n)	直观易懂，容易实现	不符合题目的常量空间要求
位运算	O(n)	O(1)	满足题目要求，高效优雅	需要深入理解位运算性质
排序后遍历	O(n log n)	O(1)	实现相对简单	时间复杂度不满足线性要求

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第260题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

示例 3：

提示

解题思路

方法一：哈希表

方法二：位运算

关键点

具体步骤

复杂度分析

图解思路

算法步骤分析表

位运算分组原理表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流