1. 概述
在本文中，我们将探讨一个经典问题：在一个元素两两成对的数组中，找出唯一一个没有配对的元素。我们将通过示例说明问题，并提供三种不同的解决思路。
文章重点如下：
✅ 问题定义与示例
✅ 暴力解法（O(N²)）
✅ 使用 Map（O(N)）
✅ 使用位运算 XOR（O(N)，最优解）
2. 问题定义
给定一个大小为 N 的整型数组 A，其中 N 为奇数。数组中除了一个元素外，其余每个元素都恰好出现两次。我们的任务是找出那个只出现一次、无法配对的元素。
例如，考虑以下数组：
尝试两两配对：
可以看到 4、3、1 都能成对，只有 2 是孤立的。因此，答案是 2。
3. 暴力解法（O(N²)）
思路：
对每个元素，遍历整个数组寻找它的配对项。如果找不到，说明就是目标元素。
实现：
algorithm NaiveApproach(A, N):
for i <- 1 to N:
isPaired <- false
for j <- 1 to N:
if i != j and A[i] == A[j]:
isPaired <- true
break
if not isPaired:
return A[i]
return -1
说明：
- 时间复杂度：**O(N²)**，效率较低
- 空间复杂度：O(1)
⚠️ 适用于小数据集，不推荐用于大规模数据
4. 使用 Map（O(N)）
思路：
使用 Map（或 HashMap）记录每个元素出现的次数，最后遍历 Map 找出出现次数为 1 的元素。
实现：
algorithm MapApproach(A, N):
map <- create an empty map
for i <- 1 to N:
map[A[i]] <- map[A[i]] + 1
for element in map:
if element.value == 1:
return element.key
return -1
说明：
- 时间复杂度：O(N)
- 空间复杂度：O(N)
✅ 适用于大多数场景，但需要额外空间
5. 使用 XOR 位运算（O(N)，最优解）
5.1 原理
XOR 位运算具有以下性质：
- X ^ Y = Y ^ X
- X ^ X = 0
- 0 ^ X = X
因此，如果我们将数组中所有元素进行 XOR 操作，成对的元素会被抵消为 0，剩下的就是那个唯一未配对的元素。
举例：
假设数组为 [4, 3, 1, 2, 1, 3, 4]，则：
4 ^ 3 ^ 1 ^ 2 ^ 1 ^ 3 ^ 4
= (4 ^ 4) ^ (3 ^ 3) ^ (1 ^ 1) ^ 2
= 0 ^ 0 ^ 0 ^ 2
= 2
5.2 实现：
algorithm XORApproach(A, N):
answer <- 0
for i <- 1 to N:
answer <- answer XOR A[i]
return answer
说明：
- 时间复杂度：O(N)
- 空间复杂度：O(1)
✅ 最优解法，推荐使用
6. 总结
| 方法 | 时间复杂度 | 空间复杂度 | 是否推荐 |
|---|---|---|---|
| 暴力解法 | O(N²) | O(1) | ❌ |
| 使用 Map | O(N) | O(N) | ✅ |
| 使用 XOR | O(N) | O(1) | ✅✅✅ |
✅ XOR 解法是本问题的最佳解法，兼具时间和空间优势
✅ 掌握 XOR 的性质在面试中非常实用，建议熟练掌握
⚠️ 注意：该问题前提是只有一个元素未配对，如果有多个则 XOR 方法不再适用