当前位置：首页 > ds >正文

LeetCode 136：只出现一次的数字 - 巧用异或运算的极致解法

ds 2025/8/26 11:41:56

文章目录

- 问题描述
- 解题思路：异或运算的巧妙应用
- - 异或运算的核心特性
  - 算法核心思想
- Java代码实现
- 复杂度分析
- 原理解析
- 边界条件测试
- 实际应用场景
- 总结

本文讲解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
}