本文探讨了如何在java中使用集合高效地从数组中提取重复元素，只保留重复项中的一个副本。通过利用`hashset`的`o(1)`平均时间复杂度特性来跟踪已遇到的元素，并结合`arraylist`收集重复项，该方法避免了传统嵌套循环带来的`o(n^2)`性能瓶颈，实现了更优的`o(n)`解决方案，从而有效地处理了如`{1,1,2,2,2}`返回`{1,2,2}`的需求。
1. 问题描述
在Java编程中，我们经常需要处理数组或列表中重复元素的问题。一个常见的需求是，给定一个包含重复元素的列表，需要返回所有重复的元素，但每个重复的元素只返回其出现次数减一的副本。例如，如果输入列表为{1,1,2,2,2}，期望的输出是{1,2,2}。这意味着对于数字1（出现2次），返回1次；对于数字2（出现3次），返回2次。
2. 传统方法的局限性
一种直观但效率不高的方法是使用嵌套循环。例如，通过遍历列表中的每个元素，然后再次遍历列表检查是否存在相同的元素，并使用一个额外的列表来存储已经发现的唯一重复元素。
public static Integer[] returnDuplicateInefficient(Integer[] list) {
List uniqueList = new ArrayList<>();
for (int k = 0; k < list.length; k++) {
for (int j = 0; j < list.length; j++) {
// 检查当前元素与另一个元素是否相同，且不是同一个索引，并且该元素尚未被添加到uniqueList中
if (list[k] == list[j] && k != j && !uniqueList.contains(list[k])) {
uniqueList.add(list[k]);
}
}
}
// 将List转换为Integer数组
return uniqueList.toArray(new Integer[0]);
} 这种方法的缺点在于其性能。uniqueList.contains(list[k])操作在ArrayList中需要遍历整个列表来查找元素，其时间复杂度为O(n)。由于外层和内层循环都是O(n)，导致整体时间复杂度达到O(n^3)，或者至少是O(n^2)（如果uniqueList的contains操作效率更高，但通常仍是O(n)），这对于大型数据集来说是不可接受的。此外，这种方法只能返回每个重复元素的一个实例（例如，{1,1,2,2,2}返回{1,2}），不符合题目要求。
3. 基于 HashSet 的高效解决方案
为了解决上述问题并满足“返回重复元素副本数减一”的需求，我们可以利用Java集合框架中的HashSet。HashSet的add()方法在平均情况下具有O(1)的时间复杂度，这比ArrayList的contains()方法（O(n)）效率高得多。
立即学习“Java免费学习笔记（深入）”；
核心思想：
- 维护一个HashSet来记录已经“见过”的元素。
- 遍历输入数组中的每个元素。
- 尝试将当前元素添加到HashSet中。
- 如果Set.add(element)方法返回true，说明这个元素是第一次被添加到Set中，它是一个新的唯一元素。
- 如果Set.add(element)方法返回false，说明这个元素已经在Set中存在，因此它是一个重复元素。此时，我们将其添加到结果列表中。
这样，对于第一次出现的元素，它会被添加到HashSet中。对于第二次及以后出现的相同元素，Set.add()会返回false，从而将其识别为重复项并加入到结果列表中。这完美地符合了“返回重复元素副本数减一”的要求。
3.1 示例代码
以下是使用HashSet实现上述逻辑的Java方法：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class DuplicateElementExtractor {
/**
* 从给定的Integer数组中提取重复元素，每个重复元素只保留其出现次数减一的副本。
* 例如，输入 {1, 1, 2, 2, 2} 将返回 {1, 2, 2}。
*
* @param list 包含可能重复元素的Integer数组。
* @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.add(next); // 将重复元素添加到结果列表
}
}
// 将List转换为Integer数组并返回
return duplicates.toArray(new Integer[0]); // 使用toArray(T[]::new) 更简洁
}
public static void main(String[] args) {
Integer[] testList1 = {1, 1, 2, 2, 2};
System.out.println("输入: " + Arrays.toString(testList1) + " -> 输出: " + Arrays.toString(returnDuplicates(testList1))); // 预期输出: [1, 2, 2]
Integer[] testList2 = {3, 4, 5, 3, 4, 6, 7, 7, 7};
System.out.println("输入: " + Arrays.toString(testList2) + " -> 输出: " + Arrays.toString(returnDuplicates(testList2))); // 预期输出: [3, 4, 7, 7]
Integer[] testList3 = {10, 20, 30};
System.out.println("输入: " + Arrays.toString(testList3) + " -> 输出: " + Arrays.toString(returnDuplicates(testList3))); // 预期输出: []
Integer[] testList4 = {1, 1, 1, 1};
System.out.println("输入: " + Arrays.toString(testList4) + " -> 输出: " + Arrays.toString(returnDuplicates(testList4))); // 预期输出: [1, 1, 1]
}
} 3.2 代码解析
-
List
duplicates = new ArrayList(); : 创建一个ArrayList来存储所有被识别为重复的元素。这是最终需要返回的结果列表。 -
Set
seen = new HashSet(); : 创建一个HashSet。HashSet的特点是它只存储唯一的元素，并且提供非常快速的查找、添加和删除操作（平均时间复杂度为O(1)）。 - for (Integer next : list): 使用增强型for循环遍历输入数组list中的每一个元素。
-
if (!seen.add(next)): 这是核心逻辑。
- seen.add(next)尝试将当前元素next添加到seen集合中。
- 如果next是第一次出现在seen集合中，add()方法会成功添加并返回true。
- 如果next已经存在于seen集合中（即它是一个重复元素），add()方法不会添加它（因为Set不允许重复），并返回false。
- 因此，!seen.add(next)为true的条件表示当前元素next是一个重复元素（至少是第二次出现）。
- duplicates.add(next);: 当!seen.add(next)为true时，我们将这个重复元素添加到duplicates列表中。
- return duplicates.toArray(new Integer[0]);: 最后，将存储重复元素的duplicates列表转换为Integer数组并返回。new Integer[0]是一个推荐的用法，它会根据列表的大小自动创建一个新的数组。
4. 性能分析
- 时间复杂度： 遍历输入数组一次，每次迭代中HashSet的add()操作平均时间复杂度为O(1)。因此，整个方法的时间复杂度为O(n)，其中n是输入数组的长度。这比O(n^2)或O(n^3)的传统方法有了显著的提升。
- 空间复杂度： HashSet和ArrayList在最坏情况下可能需要存储所有n个元素（例如，所有元素都是唯一的，或者所有元素都是重复的）。因此，空间复杂度为O(n)。
5. 注意事项
- 泛型类型： 本教程示例使用的是Integer数组。对于其他对象类型，需要确保它们正确地实现了hashCode()和equals()方法，以便HashSet能够正确地判断对象的相等性。
- 基本类型数组： 如果输入是基本类型数组（如int[]），需要先将其转换为包装类数组（Integer[]）才能使用Collection框架。
- Null值处理： HashSet允许存储null值，但只允许一个。如果输入数组可能包含多个null值，并且您希望将它们视为重复项，此方法也能正确处理。
6. 总结
通过巧妙地利用HashSet的O(1)平均时间复杂度的add()方法特性，我们可以高效地从Java数组中提取重复元素，并精确地控制每个重复项的副本数量。这种方法在性能上远优于简单的嵌套循环，是处理此类重复元素问题的推荐实践。理解并运用Java集合框架的特性，能够帮助我们编写出更高效、更健壮的代码。
