本文探讨了在java中如何高效地识别并返回列表中的重复元素，但仅保留每个重复元素除首次出现外的所有副本。通过利用`hashset`的`o(1)`平均时间复杂度特性，我们可以避免传统嵌套循环或`arraylist.contains()`带来的`o(n^2)`性能瓶颈。核心思想是迭代列表，尝试将元素添加到`hashset`，若添加失败则说明该元素是重复出现，将其加入结果列表，从而实现`o(n)`时间复杂度的优化。
1. 问题背景与需求分析
在数据处理中，我们经常需要从一个集合中识别并提取重复的元素。然而，具体的需求可能有所不同。例如，给定一个整数数组 [1, 1, 2, 2, 2]，我们的目标不是简单地返回所有不同的重复元素（即 [1, 2]），而是返回除去每个重复元素首次出现之外的所有副本，即 [1, 2, 2]。这意味着对于数字 1，它出现了两次，我们需要返回一个 1；对于数字 2，它出现了三次，我们需要返回两个 2。
传统的嵌套循环结合 ArrayList.contains() 的方法虽然可以找出唯一的重复元素，但存在两个主要问题：
- 性能低下： ArrayList.contains() 操作在最坏情况下需要遍历整个列表，时间复杂度为 O(n)。在一个嵌套循环中，整体时间复杂度将达到 O(n^2)，这对于大型数据集是不可接受的。
- 结果不准确： 这种方法通常只会将首次发现的重复元素添加一次，导致无法满足“返回所有副本减一”的需求。例如，对于 [1,1,2,2,2]，它只会返回 [1,2]。
2. 优化方案：利用 HashSet 高效识别重复元素
为了高效且准确地解决上述问题，我们可以利用 Java 集合框架中的 HashSet。HashSet 是一种基于哈希表的集合，它只存储唯一的元素，并且其 add() 和 contains() 等操作的平均时间复杂度为 O(1)。
2.1 核心思想
该方法的核心思想是：
立即学习“Java免费学习笔记（深入）”；
- 维护一个 HashSet 来记录所有已经“见过”的元素。
- 遍历原始数组中的每个元素。
- 尝试将当前元素添加到 HashSet 中。
- 如果 HashSet.add(element) 返回 true，表示该元素是第一次被添加到 HashSet 中（即它是第一次出现）。
- 如果 HashSet.add(element) 返回 false，表示该元素在 HashSet 中已经存在（即它不是第一次出现，而是重复出现）。此时，我们知道这是一个重复的元素，并且是其第一次出现后的一个副本，因此将其添加到我们的结果列表中。
2.2 示例代码
以下是实现这一逻辑的 Java 代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class DuplicateElementExtractor {
/**
* 从给定的整数数组中提取重复元素，每个重复元素只保留其首次出现后的所有副本。
* 例如，输入 [1, 1, 2, 2, 2]，输出 [1, 2, 2]。
*
* @param list 待处理的整数数组。
* @return 包含重复元素的列表，以 Integer 数组形式返回。
*/
public static Integer[] returnDuplicates(Integer[] list) {
// 用于存储识别到的重复元素
List duplicates = new ArrayList<>();
// 用于高效记录已经见过的唯一元素
Set seen = new HashSet<>();
// 遍历输入数组中的每一个元素
for (Integer next : list) {
// 尝试将当前元素添加到 seen 集合中
// 如果 add() 方法返回 false，说明元素已经存在于 seen 集合中，
// 意味着当前元素是一个重复项（非首次出现）
if (!seen.add(next)) {
// 将这个重复项添加到 duplicates 列表中
duplicates.add(next);
}
}
// 将结果列表转换为 Integer 数组并返回
return duplicates.toArray(new Integer[0]);
}
public static void main(String[] args) {
Integer[] testList1 = {1, 1, 2, 2, 2};
System.out.println("Input: " + Arrays.toString(testList1) + ", Output: " + Arrays.toString(returnDuplicates(testList1))); // 预期输出: [1, 2, 2]
Integer[] testList2 = {3, 4, 5, 3, 4, 6, 7, 3};
System.out.println("Input: " + Arrays.toString(testList2) + ", Output: " + Arrays.toString(returnDuplicates(testList2))); // 预期输出: [3, 4, 3]
Integer[] testList3 = {10, 20, 30};
System.out.println("Input: " + Arrays.toString(testList3) + ", Output: " + Arrays.toString(returnDuplicates(testList3))); // 预期输出: []
}
} 2.3 代码解析
-
List
duplicates = new ArrayList(); : 这个 ArrayList 用于收集所有满足条件的重复元素。每次 HashSet.add() 返回 false 时，该元素就会被添加到这个列表中。 -
Set
seen = new HashSet(); : 这个 HashSet 是实现高效去重的关键。它存储所有在遍历过程中已经出现过的唯一元素。由于 HashSet 内部使用哈希表，其 add() 操作的平均时间复杂度为 O(1)。 - for (Integer next : list): 这是一个增强型 for 循环，用于遍历输入数组 list 中的每一个元素。
-
if (!seen.add(next)): 这是核心逻辑。
- seen.add(next) 尝试将 next 元素添加到 seen 集合中。
- 如果 next 之前不在 seen 集合中，add() 方法会成功添加并返回 true。
- 如果 next 已经存在于 seen 集合中（即它是一个重复元素），add() 方法不会再次添加，并返回 false。
- !seen.add(next) 意味着当 add() 返回 false 时（即发现重复元素时），条件成立。
- duplicates.add(next);: 当 !seen.add(next) 条件为真时，说明当前 next 元素是其首次出现后的一个副本，因此将其添加到 duplicates 列表中。
- return duplicates.toArray(new Integer[0]);: 最后，将收集到的 duplicates 列表转换为 Integer 类型的数组并返回。new Integer[0] 作为一个参数，是为了指定返回数组的类型，并优化内存分配。
3. 性能分析
使用 HashSet 的方法具有显著的性能优势：
- 时间复杂度： 遍历输入数组一次，对于每个元素，HashSet.add() 操作的平均时间复杂度为 O(1)。因此，整个算法的平均时间复杂度为 O(n)，其中 n 是输入数组的长度。这比 O(n^2) 的嵌套循环方法要高效得多。
- 空间复杂度： HashSet 和 ArrayList 都可能需要存储最多 n 个元素（在所有元素都唯一或所有元素都重复的极端情况下）。因此，空间复杂度为 O(n)。
4. 注意事项与总结
- 泛型支持： 上述方法可以很容易地扩展到其他对象类型，只需将 Integer 替换为相应的泛型类型 T 即可，前提是这些对象类型正确实现了 hashCode() 和 equals() 方法，以确保 HashSet 能正确识别它们的唯一性。
- 元素顺序： 此方法返回的重复元素列表的顺序与它们在原始数组中作为重复项出现的顺序一致。
- 选择合适的集合： HashSet 是处理唯一性检查的理想选择，但在其他场景下，如需要保持插入顺序或进行排序时，可能需要考虑 LinkedHashSet 或 TreeSet。
通过采用 HashSet，我们能够以线性时间复杂度高效地解决在 Java 中识别并返回特定重复元素副本的问题，避免了传统方法带来的性能瓶颈，并确保了结果的准确性。这种模式在处理大规模数据集时尤为重要。
