在Java中查找List中的所有重复元素

1. 引言

本文将探讨在Java中查找List中重复元素的多种方法。给定一个包含重复元素的整数列表（例如[1, 2, 3, 3, 4, 4, 5]），我们需要提取出其中的重复元素（即[3, 4]）。这些方法各有优劣，适用于不同场景。

2. 使用集合框架查找重复元素

2.1. 利用Set的contains()方法

Java中的Set不允许重复元素，其contains()方法能快速判断元素是否存在。我们可以利用这个特性：

List<Integer> listDuplicateUsingSet(List<Integer> list) {
    List<Integer> duplicates = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    for (Integer i : list) {
        if (set.contains(i)) {
            duplicates.add(i);
        } else {
            set.add(i);
        }
    }
    return duplicates;
}

测试验证：

@Test
void givenList_whenUsingSet_thenReturnDuplicateElements() {
    List<Integer> list = Arrays.asList(1, 2, 3, 3, 4, 4, 5);
    List<Integer> duplicates = listDuplicate.listDuplicateUsingSet(list);
    Assert.assertEquals(duplicates.size(), 2);
    Assert.assertTrue(duplicates.contains(3));
    Assert.assertTrue(duplicates.contains(4));
    Assert.assertFalse(duplicates.contains(1));
}

✅ 优点：时间复杂度O(n)，空间复杂度O(n)
❌ 缺点：需要额外存储空间

2.2. 使用Map统计元素频率

通过Map记录每个元素的出现次数，再筛选出次数>1的元素：

List<Integer> listDuplicateUsingMap(List<Integer> list) {
    List<Integer> duplicates = new ArrayList<>();
    Map<Integer, Integer> frequencyMap = new HashMap<>();
    for (Integer number : list) {
        frequencyMap.put(number, frequencyMap.getOrDefault(number, 0) + 1);
    }
    for (int number : frequencyMap.keySet()) {
        if (frequencyMap.get(number) != 1) {
            duplicates.add(number);
        }
    }
    return duplicates;
}

测试验证：

@Test
void givenList_whenUsingFrequencyMap_thenReturnDuplicateElements() {
    List<Integer> list = Arrays.asList(1, 2, 3, 3, 4, 4, 5);
    List<Integer> duplicates = listDuplicate.listDuplicateUsingMap(list);
    Assert.assertEquals(duplicates.size(), 2);
    Assert.assertTrue(duplicates.contains(3));
    Assert.assertTrue(duplicates.contains(4));
    Assert.assertFalse(duplicates.contains(1));
}

✅ 优点：逻辑清晰，时间复杂度O(n)
❌ 缺点：需要遍历两次（一次统计，一次筛选）

3. 使用Java 8 Stream API

3.1. 结合filter()和Set.add()

利用Set.add()的返回值（添加成功返回true）进行筛选：

List<Integer> listDuplicateUsingFilterAndSetAdd(List<Integer> list) {
    Set<Integer> elements = new HashSet<>();
    return list.stream()
      .filter(n -> !elements.add(n))
      .collect(Collectors.toList());
}

测试验证：

@Test
void givenList_whenUsingFilterAndSetAdd_thenReturnDuplicateElements() {
    List<Integer> list = Arrays.asList(1, 2, 3, 3, 4, 4, 5);
    List<Integer> duplicates = listDuplicate.listDuplicateUsingFilterAndSetAdd(list);
    Assert.assertEquals(duplicates.size(), 2);
    Assert.assertTrue(duplicates.contains(3));
    Assert.assertTrue(duplicates.contains(4));
    Assert.assertFalse(duplicates.contains(1));
}

⚠️ 注意：这是最快的方法之一，时间复杂度O(n)，空间复杂度O(n)

3.2. 使用Collections.frequency()

通过Collections.frequency()统计元素频率，但性能较差：

List<Integer> listDuplicateUsingCollectionsFrequency(List<Integer> list) {
    return list.stream()
      .filter(i -> Collections.frequency(list, i) > 1)
      .distinct()
      .collect(Collectors.toList());
}

测试验证：

@Test
void givenList_whenUsingCollectionsFrequency_thenReturnDuplicateElements() {
    List<Integer> list = Arrays.asList(1, 2, 3, 3, 4, 4, 5);
    List<Integer> duplicates = listDuplicate.listDuplicateUsingCollectionsFrequency(list);
    Assert.assertEquals(duplicates.size(), 2);
    Assert.assertTrue(duplicates.contains(3));
    Assert.assertTrue(duplicates.contains(4));
    Assert.assertFalse(duplicates.contains(1));
}

❌ 缺点：时间复杂度O(n²)，不适合大数据量

3.3. 使用Collectors.groupingBy()

通过分组统计元素频率，再筛选重复项：

List<Integer> listDuplicateUsingMapAndCollectorsGroupingBy(List<Integer> list) {
    return list.stream()
      .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
      .entrySet()
      .stream()
      .filter(m -> m.getValue() > 1)
      .map(Map.Entry::getKey)
      .collect(Collectors.toList());
}

测试验证：

@Test
void givenList_whenUsingMapAndCollectorsGroupingBy_thenReturnDuplicateElements() {
    List<Integer> list = Arrays.asList(1, 2, 3, 3, 4, 4, 5);
    List<Integer> duplicates = listDuplicate.listDuplicateUsingMapAndCollectorsGroupingBy(list);
    Assert.assertEquals(duplicates.size(), 2);
    Assert.assertTrue(duplicates.contains(3));
    Assert.assertTrue(duplicates.contains(4));
    Assert.assertFalse(duplicates.contains(1));
}

✅ 优点：代码简洁，时间复杂度O(n)
⚠️ 注意：需要理解Stream操作链

4. 查找数组中的重复元素

4.1. 使用循环检测

public static Set<Integer> findDuplicateInArray(int[] array) {
    Set<Integer> duplicates = new HashSet<>();
    Set<Integer> seen = new HashSet<>();
    for (int val : array) {
        if (!seen.add(val)) {
            duplicates.add(val);
        }
    }
    return duplicates;
}

4.2. 使用Stream API

public static <T> Set<T> findDuplicateInArrayWithStream(T[] array) {
    Set<T> seen = new HashSet<>();
    return Arrays.stream(array)
      .filter(val -> !seen.add(val))
      .collect(Collectors.toSet());
}

✅ 优点：现代Java风格，代码简洁
⚠️ 注意：适用于对象数组，基本类型需转换

5. 总结

本文介绍了在Java中查找重复元素的多种方法：

方法	时间复杂度	空间复杂度	适用场景
Set.contains()	O(n)	O(n)	简单场景
Map统计频率	O(n)	O(n)	需要频率信息
Stream+Set.add()	O(n)	O(n)	推荐，性能最佳
Collections.frequency()	O(n²)	O(n)	避免使用
Collectors.groupingBy()	O(n)	O(n)	复杂流处理

最佳实践：

• 优先使用Stream+Set.add()方法（3.1节），性能和可读性俱佳
• 避免使用Collections.frequency()，性能太差
• 处理数组时，Stream API更简洁（4.2节）

完整代码示例可在GitHub获取，如有问题可联系example@baeldung.com。