企业官网建设流程全解析

本文概览：本文讲解只出现一次的数字：其余数字都出现两次，异或运算满足 a^a=0、a0=a 且可交换可结合，把所有数字全异或一遍，成对的互相抵消成 0，剩下的就是答案。用二进制逐位演示抵消过程，O(n) 时间、O(1) 空间

一、题目

二、题目分析

1. 题目要求

给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

进阶要求：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1：nums = [2, 2, 1]→ 1

示例 2：nums = [4, 1, 2, 1, 2]→ 4

示例 3：nums = [1]→ 1

2. 怎么想这题？

题目给出的条件里有个关键信息：除了答案，其他数字都是成对出现的。

那最直观的思路就来了——怎么把"成对"的数字消掉、只留下那个落单的？顺着这个想法，有几条路可以走：

• 用哈希集合把出现过的数字记下来：第一次遇到就放进去，第二次遇到就说明它成对了，从集合里删掉。最后集合里剩下的就是那个落单的。这条路好想，但要多花 O(n) 的空间。
• 排序之后两两比较，成对的会挨在一起，扫一遍就能找出落单的。这是 O(n log n)，也没达到"线性"的要求。
• 有没有一种运算，天生就能让两个相同的数互相抵消？有，就是异或。它比前两条路都好，因为既快又不需要额外空间。

3. 需要解决哪几个问题？

问题一：哈希集合和排序这两条路，为什么达不到题目"线性 + 不用额外空间"的要求？

问题二（核心）：异或为什么能让相同的数字互相抵消？从二进制位上到底发生了什么？

问题三：为什么把所有数字一股脑异或起来（完全不管顺序）也能得出正确答案？

三、方法一：哈希集合，O(n) 空间

1. 思路概览

publicintsingleNumber(int[]nums){Set<Integer>set=newHashSet<>();for(intnum:nums){if(!set.add(num)){// add 返回 false 说明这个数已经在集合里了，是对里的第二个set.remove(num);}}returnset.iterator().next();}

思路简要说明：

1. 进进出出：第一次遇到某个数就放进去，第二次遇到（add返回false）说明它成对了，从集合里移走
2. 剩下的就是答案：所有成对的都被移走了，集合里只剩那个落单的
3. 时间复杂度 O(n)，空间 O(n)
4. 不满足进阶要求：用了 O(n) 的额外空间

2. 思路详解

这个思路就是拿集合模拟"配对"的过程。set.add(num)会返回一个布尔值：放进去之前集合里没有这个数就返回true，已经有了就返回false。所以：

• 第一次遇到4：集合里没有 →add返回true→ 留着；
• 第二次遇到4：集合里已经有了 →add返回false→ 说明这一对凑齐了，两个一起消掉（把4从集合里remove）。

以[4, 1, 2, 1, 2]为例：

遇到 4：set = [4] 遇到 1：set = [4, 1] 遇到 2：set = [4, 1, 2] 遇到 1：1 已存在 → set = [4, 2] 遇到 2：2 已存在 → set = [4] 返回 4 ✓

逻辑很直白，代价是那个集合占用了 O(n) 的空间——题目偏偏要求"不使用额外空间"。

3. 复杂度分析

时间复杂度 O(n)：遍历一次，哈希操作均摊 O(1)。

空间复杂度 O(n)：最坏情况下集合里存近 n 个数。

四、方法二：排序后两两比较，O(n log n)

1. 思路概览

publicintsingleNumber(int[]nums){Arrays.sort(nums);for(inti=0;i+1<nums.length;i+=2){if(nums[i]!=nums[i+1]){returnnums[i];}}returnnums[nums.length-1];}

思路简要说明：

1. 排序让成对的数字挨在一起：排完之后相同的数一定相邻
2. 两两跳着扫：每次看一对(nums[i], nums[i+1])，不相等说明nums[i]就是落单的
3. 扫完没找到：说明落单的是最后一个元素
4. 时间复杂度 O(n log n)，空间 O(1)（不算排序本身的开销）

2. 思路详解

排序会把相等的元素排到一起，所以数组变成"一对、一对……最后可能单一个"的样子。于是从下标 0 开始，每次跨两步看一对：

• 如果这一对相等，说明这对配上了，往后跳两步继续；
• 如果这一对不相等，说明前一个数没有同伴——它就是答案。

用[4, 1, 2, 1, 2]举例，排序后是[1, 1, 2, 2, 4]：

i=0：nums[0]=1 和 nums[1]=1 相等 → 跳过 i=2：nums[2]=2 和 nums[3]=2 相等 → 跳过 i=4：i+1 越界，循环结束 → 返回最后一个 4 ✓

这个方法空间省了，但排序要 O(n log n)，比线性的要求慢一截。

3. 复杂度分析

时间复杂度 O(n log n)：排序占主要开销。

空间复杂度 O(1)：只用了下标变量。

五、方法三：异或，O(n) 时间 + O(1) 空间

1. 思路概览

publicintsingleNumber(int[]nums){intans=0;for(intnum:nums){ans^=num;}returnans;}

思路简要说明：

1. 一个变量一路异或到底：ans从 0 开始，把每个数都异或进去
2. 成对的自动抵消：两个相同的数异或得 0，等于没参与
3. 剩下的就是答案：所有成对数字抵消完，ans里留下的只有那个落单的
4. 时间复杂度 O(n)，空间 O(1)

2. 思路详解

第一步：解决"为什么异或能抵消"——先看异或在二进制位上的规则

异或（^）是按位运算：先把两个数都写成二进制，再让它们一位对齐一位地算。因为是二进制，每一位上只可能是 0 或 1 两种值，两个位碰在一起一共也只有四种组合，规则就两条：

相同得 0：0 ^ 0 = 0 1 ^ 1 = 0 不同得 1：0 ^ 1 = 1 1 ^ 0 = 1

这里要特别注意，上面式子里的 0 和 1 全都是二进制位（bit）上的值，说的是"这一位取 0 还是取 1"，不是十进制的数字 0 和 1。所以这四行的意思是：把某一位上的两个 bit 做异或，得到的结果 bit是 0 还是 1——两个 bit 相同，结果 bit 就是 0；两个 bit 不同，结果 bit 就是 1。

一句话记住：“相同得 0，不同得 1”。

由此立刻能推出两个性质：

a ^ a = 0 ← 两个一模一样的数，每一位上的两个 bit 都相同，逐位算出来都是 bit 0；一位一位全是 0，整个数就是 0 a ^ 0 = a ← 每一位拿 bit 和 0 去比：原来是 bit 1 的"不同得 1"，原来是 bit 0 的"相同得 0"，结果原样不动

第一个性质正是我们想要的：两个相同的数异或，结果就是 0，等于互相抵消没出现过。

第二步：把示例 2 拆成二进制看抵消过程

拿nums = [4, 1, 2, 1, 2]来，先把每个数写成二进制：

4 = 1 0 0 1 = 0 0 1 2 = 0 1 0 1 = 0 0 1 2 = 0 1 0

现在一位一列地竖着看，每一位各自做异或：

位2 位1 位0 4 1 0 0 1 0 0 1 2 0 1 0 1 0 0 1 2 0 1 0 ------------------------ 结果 1 0 0 = 4

逐位解释：

• 位 0：这一列是0、1、0、1、0。两个1来自那两个1，异或时1 ^ 1 = 0，正好抵消，最后剩 0。
• 位 1：这一列是0、0、1、0、1。两个1来自那两个2，同样抵消，剩 0。
• 位 2：这一列是1、0、0、0、0。只有4贡献了一个1，没有谁能和它抵消，于是留下 1。

三位合起来1 0 0，正是 4——那个落单的数。

换一个角度：把整个异或过程一步步算出来

ans 初始 = 000 ans ^ 4 = 000 ^ 100 = 100 → 4 ans ^ 1 = 100 ^ 001 = 101 → 5 ans ^ 2 = 101 ^ 010 = 111 → 7 ans ^ 1 = 111 ^ 001 = 110 → 6 ans ^ 2 = 110 ^ 010 = 100 → 4 ✓

中间几步的ans是 5、7、6，看着毫无规律，但那只是"还没配上对"的临时状态。等到把1和1、2和2都异或进去，它们两两抵消，最后只剩 4。

这也说明一件事：不需要关心中间过程是什么，只要保证每个数字都被异或了一次，成对的就会自己消掉。

第三步：解决"为什么可以不管顺序"

异或满足交换律（a ^ b = b ^ a）和结合律（(a ^ b) ^ c = a ^ (b ^ c)）。

原因从"按位独立"就能看出来：异或的每一位各算各的，不同位之间互不影响。而单独看某一位，这一位上无非是一堆 0 和 1，1的个数是偶数就全抵消、是奇数就留一个 1——数一数就行，跟谁先谁后毫无关系。

所以整个数组可以看成"所有数字一起异或"，怎么打乱顺序、怎么分组都行：

4 ^ 1 ^ 2 ^ 1 ^ 2 = (1 ^ 1) ^ (2 ^ 2) ^ 4 ← 用交换律结合律把成对的挪到一起 = 0 ^ 0 ^ 4 = 4

成对的都变成了 0，0 ^ 4 = 4（a ^ 0 = a），答案就浮出来了。

第四步：代码细节

intans=0;// 从 0 开始，因为 0 异或任何数都是那个数本身（0 ^ x = x）for(intnum:nums){ans^=num;// 逐个异或进去}returnans;

• 为什么初值是 0：0 ^ x = x，0 是异或运算的"零元"，拿它起步不会影响结果。
• 数组只有一个元素：循环走一遍，ans = 0 ^ nums[0] = nums[0]，直接返回它自己，符合预期。
• 负数也没问题：异或是补码上按位算的，性质a ^ a = 0、a ^ 0 = a对负数一样成立。

3. 复杂度分析

时间复杂度 O(n)：一次遍历，每个数只做一次异或。

空间复杂度 O(1)：只用一个变量ans。

六、总结

这题的关键在于抓住"其余元素都出现两次"这个条件，然后找到一种"相同的两个数碰一起就消失"的运算——异或正好就是：

• a ^ a = 0：成对的自动抵消；
• a ^ 0 = a：落单的不受影响；
• 可交换、可结合：所以能无视顺序，从头到尾一把梭。

前两种方法都能算出答案，但一个要多花空间、一个要多花时间；异或同时把时间和空间都做到了最优，而且代码只有三行。