本文讲解LeetCode第136题"只出现一次的数字"，展示如何利用异或运算的巧妙特性在O(n)时间复杂度和O(1)空间复杂度内解决该问题。
问题描述
给定一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例：
输入: [2,2,1]
输出: 1
输入: [4,1,2,1,2]
输出: 4
要求：
- 算法应具有线性时间复杂度O(n)
- 不使用额外空间实现（即空间复杂度O(1)）
解题思路：异或运算的巧妙应用
这道题的难点在于严格的空间复杂度限制，常规解法（如使用哈希表）虽然能达到O(n)时间复杂度，但需要O(n)的额外空间。而使用异或运算（XOR）可以完美解决这个问题。
异或运算的核心特性
归零律：任何数与自身异或结果为0
a ⊕ a = 0恒等律：任何数与0异或结果为其本身
a ⊕ 0 = a交换律与结合律：
a ⊕ b = b ⊕ a
(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
算法核心思想
利用异或运算的特性：
- 数组中成对出现的数字异或后会相互抵消（结果为0）
- 所有数字异或后，最终结果就是唯一出现一次的数字
计算过程模拟：
[4, 1, 2, 1, 2]
= 4 ⊕ (1 ⊕ 1) ⊕ (2 ⊕ 2)
= 4 ⊕ 0 ⊕ 0
= 4
Java代码实现
public class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num; // 异或运算
}
return result;
}
}
复杂度分析
时间复杂度：O(n)
只需遍历数组一次，每个元素执行一次异或操作空间复杂度：O(1)
仅使用一个额外变量存储结果，与输入规模无关
原理解析
- 初始化：
result = 0（0与任何数异或等于该数本身） - 遍历过程：
- 遇到第一次出现的数：存储到result中（0 ⊕ a = a）
- 遇到第二次出现的相同数：消除该数的影响（a ⊕ a = 0）
- 最终结果：所有成对数字抵消为0，唯一数保留在result中
边界条件测试
public static void main(String[] args) {
Solution solution = new Solution();
// 测试用例1：唯一数在开头
int[] nums1 = {4, 1, 2, 1, 2};
System.out.println("测试1: " + solution.singleNumber(nums1)); // 输出4
// 测试用例2：唯一数在结尾
int[] nums2 = {1, 3, 1, 3, 2};
System.out.println("测试2: " + solution.singleNumber(nums2)); // 输出2
// 测试用例3：负数测试
int[] nums3 = {-5, 3, 3, -5, 7};
System.out.println("测试3: " + solution.singleNumber(nums3)); // 输出7
// 测试用例4：单个元素
int[] nums4 = {6};
System.out.println("测试4: " + solution.singleNumber(nums4)); // 输出6
}
实际应用场景
- 数据校验：网络传输中检测数据包是否丢失
- 加密算法：对称加密中的简单异或加密
- 并行计算：快速比较两组数据差异
- 硬件编程：嵌入式系统中的状态切换
总结
- 异或运算在解决重复元素问题中具有独特优势
- 该解法满足题目所有要求：
- O(n)时间复杂度
- O(1)空间复杂度
- 代码简洁高效（仅5行核心代码）
- 理解位运算特性可以解决许多看似复杂的问题
异或运算的其他应用：
- 不使用临时变量交换两个数
- 判断两个数是否异号
- 二进制数奇偶校验
思考题：如果数组中除了一个数出现一次，其他都出现三次，如何解决？（LeetCode 137）