1. 引言
在本教程中，我们将探讨在列表中查找第一个非重复元素的问题。首先理解问题本质，然后实现几种高效解决方案。
2. 问题陈述
给定一个元素列表，任务是找到第一个不重复的元素。核心要求：识别列表中只出现一次的首个元素。若无满足条件的元素，返回 null。
3. 使用 for 循环
这种方法通过嵌套循环暴力检查重复元素，思路简单但性能较差。
3.1. 实现
遍历每个元素，用内层循环检查其是否重复。若发现重复则跳过，否则立即返回：
Integer findFirstNonRepeating(List<Integer> list) {
for (int i = 0; i < list.size(); i++) {
int current = list.get(i);
boolean isRepeating = false;
for (int j = 0; j < list.size(); j++) {
if (i != j && current == list.get(j)) {
isRepeating = true;
break;
}
}
if (!isRepeating) {
return current;
}
}
return null;
}
以列表 [1, 2, 3, 2, 1, 4, 5, 4] 为例：
- 元素
1在索引 4 重复出现 → 跳过 - 元素
2在索引 3 重复出现 → 跳过 - 元素
3无重复 → 返回3
3.2. 复杂度分析
- ⏱️ 时间复杂度：O(n²)（嵌套循环）
- 💾 空间复杂度：O(1)（无额外空间）
⚠️ 踩坑提醒：虽然实现简单，但数据量大时性能急剧下降，生产环境慎用。
4. 使用 indexOf() 和 lastIndexOf()
通过比较元素首次和末次出现的位置判断是否重复，代码更简洁。
4.1. 实现
若元素的首次索引等于末次索引，说明唯一出现：
Integer findFirstNonRepeatedElement(List<Integer> list) {
for (int i = 0; i < list.size(); i++) {
if (list.indexOf(list.get(i)) == list.lastIndexOf(list.get(i))) {
return list.get(i);
}
}
return null;
}
以列表 [1, 2, 3, 2, 1, 4, 5, 4] 为例：
1：indexOf=0,lastIndexOf=4→ 不相等 → 跳过2：indexOf=1,lastIndexOf=3→ 不相等 → 跳过3：indexOf=2,lastIndexOf=2→ 相等 → 返回3
4.2. 复杂度分析
- ⏱️ 时间复杂度：O(n²)（每次调用
indexOf()/lastIndexOf()需遍历） - 💾 空间复杂度：O(1)
❌ 性能陷阱：看似优雅，但底层仍是 O(n²) 操作，比显式循环更隐蔽的低效。
5. 使用 HashMap
利用哈希表统计元素频率，是生产环境的首选方案。
5.1. 实现
分两步：
- 遍历列表统计频率
- 再次遍历找到首个频率为 1 的元素
Integer findFirstNonRepeating(List<Integer> list) {
Map<Integer, Integer> counts = new HashMap<>();
for (int num : list) {
counts.put(num, counts.getOrDefault(num, 0) + 1);
}
for (int num : list) {
if (counts.get(num) == 1) {
return num;
}
}
return null;
}
以列表 [1, 2, 3, 2, 1, 4, 5, 4] 为例：
- 统计频率：
{1=2, 2=2, 3=1, 4=2, 5=1} - 遍历发现
3频率为 1 → 返回3
5.2. 复杂度分析
- ⏱️ 时间复杂度：O(n)（两次线性遍历）
- 💾 空间复杂度：O(n)（存储频率表）
✅ 推荐理由：时间复杂度最优，适合大规模数据，是工业级解决方案。
6. 使用数组作为频率计数器
当元素范围有限时，可用数组替代 HashMap，避免哈希开销。
6.1. 实现
- 找到最大元素值
- 初始化频率数组
- 统计频率后查找首个唯一元素
Integer findFirstNonRepeating(List<Integer> list) {
int maxElement = Collections.max(list);
int[] frequency = new int[maxElement + 1];
for (int num : list) {
frequency[num]++;
}
for (int num : list) {
if (frequency[num] == 1) {
return num;
}
}
return null;
}
以列表 [1, 2, 3, 2, 1, 4, 5, 4] 为例：
maxElement=5→ 初始化数组[0,0,0,0,0,0]- 统计后：
[0,2,2,1,2,1] - 遍历发现
3频率为 1 → 返回3
6.2. 复杂度分析
- ⏱️ 时间复杂度：O(n)（两次线性遍历）
- 💾 空间复杂度：O(maxElement)
⚠️ 适用限制：
- 仅当元素范围较小时高效（如 1-1000）
- 若含负数或大数，会浪费内存或需额外处理
7. 方案对比
| 方法 | 时间复杂度 | 空间复杂度 | 效率 | 适用场景 |
|---|---|---|---|---|
| for 循环 | O(n²) | O(1) | ❌ 低 | 小数据量/教学演示 |
| indexOf() | O(n²) | O(1) | ❌ 低 | 代码简洁性优先 |
| HashMap | O(n) | O(n) | ✅ 高 | 通用生产环境 |
| 数组计数器 | O(n) | O(maxElement) | ✅ 高 | 元素范围有限 |
8. 结论
本文探讨了四种查找首个非重复元素的方案：
- ✅ HashMap 方案：综合最优，推荐生产使用
- ⚠️ 数组计数器：特定场景高效，但需注意元素范围
- ❌ 暴力循环：仅适用于极小数据集
开发建议：优先使用 HashMap 方案，当元素范围明确且较小时（如 ASCII 字符），可考虑数组优化。避免在性能敏感场景使用 O(n²) 方案。
示例源码见 GitHub 仓库。