Java 实例 – 查找数组中的重复元素（千字长文）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战(已更新的所有项目都能学习) / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新开坑项目:《Spring AI 项目实战》 正在持续爆肝中，基于 Spring AI + Spring Boot 3.x + JDK 21...， 点击查看 ;
• 《从零手撸：仿小红书（微服务架构）》 已完结，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

在 Java 开发中，数组是存储和操作数据的基础结构之一。然而，当数组中存在重复元素时，如何高效地识别并提取这些重复项，是开发者常遇到的挑战。无论是处理用户输入数据、分析日志文件，还是优化算法逻辑，查找数组中的重复元素都是一项核心技能。本文将通过实例演示、代码解析和性能对比，系统性地讲解这一问题的解决方法，帮助读者从基础概念逐步深入到高级优化技巧。

数组与重复元素的基础概念

什么是数组？

数组是按顺序存储同类型元素的容器，每个元素通过索引（从 0 开始）访问。例如，一个整型数组 int[] numbers = {3, 1, 4, 1, 5} 中，索引 1 的元素是 1，索引 3 的元素也是 1。当多个元素具有相同的值时，这些元素即为“重复元素”。

为什么需要查找重复元素？

重复元素可能引发逻辑错误或性能问题。例如：

• 用户注册时提交的邮箱列表中存在重复项，可能导致重复发送验证码。
• 在统计系统中，重复的计数会导致数据偏差。
• 算法竞赛中，未处理重复元素可能使排序或搜索算法效率骤降。

方法一：暴力枚举法（Brute Force Approach）

实现原理

暴力法通过双重循环遍历数组，逐个比较元素是否重复。虽然简单直接，但时间复杂度为 O(n²)，仅适用于小规模数据。

代码示例

public class DuplicateFinder {  
    public static void findDuplicatesBrute(int[] arr) {  
        for (int i = 0; i < arr.length; i++) {  
            for (int j = i + 1; j < arr.length; j++) {  
                if (arr[i] == arr[j]) {  
                    System.out.println("重复元素: " + arr[i]);  
                    break; // 避免同一元素多次打印  
                }  
            }  
        }  
    }  

    public static void main(String[] args) {  
        int[] example = {2, 3, 1, 2, 5, 3};  
        findDuplicatesBrute(example);  
    }  
}  

输出结果

重复元素: 2  
重复元素: 3  

优缺点分析

• 优点：逻辑简单，无需额外数据结构，适合理解算法基础。
• 缺点：时间效率低，当数组长度为 1000 时，需执行约 500,000 次比较。

方法二：哈希表法（Hash Table Approach）

实现原理

哈希表（如 HashMap 或 HashSet）利用键值对快速查找特性，将元素作为键存储。若插入时发现键已存在，则标记为重复。

代码示例

import java.util.HashSet;  

public class DuplicateFinder {  
    public static void findDuplicatesHash(int[] arr) {  
        HashSet<Integer> seen = new HashSet<>();  
        for (int num : arr) {  
            if (!seen.add(num)) { // add() 返回 false 表示已存在  
                System.out.println("重复元素: " + num);  
            }  
        }  
    }  

    public static void main(String[] args) {  
        int[] example = {2, 3, 1, 2, 5, 3};  
        findDuplicatesHash(example);  
    }  
}  

输出结果

重复元素: 2  
重复元素: 3  

优缺点分析

• 优点：时间复杂度 O(n)，空间复杂度 O(n)，适合中等规模数据。
• 缺点：需要额外内存存储哈希表，若内存受限需谨慎使用。

方法三：排序后遍历法（Sorting Approach）

实现原理

先对数组排序，再遍历相邻元素比较是否重复。排序后重复元素必然相邻，时间复杂度为 O(n log n)。

代码示例

public class DuplicateFinder {  
    public static void findDuplicatesSort(int[] arr) {  
        Arrays.sort(arr);  
        for (int i = 0; i < arr.length - 1; i++) {  
            if (arr[i] == arr[i + 1]) {  
                System.out.println("重复元素: " + arr[i]);  
                // 跳过连续重复项，避免重复输出  
                while (i < arr.length - 1 && arr[i] == arr[i + 1]) {  
                    i++;  
                }  
            }  
        }  
    }  

    public static void main(String[] args) {  
        int[] example = {2, 3, 1, 2, 5, 3};  
        findDuplicatesSort(example);  
    }  
}  

输出结果

重复元素: 1  
重复元素: 2  
重复元素: 3  

优缺点分析

• 优点：无需额外内存，仅需 O(1) 空间（若原地排序）。
• 缺点：修改了原数组顺序，可能破坏数据原始结构。

方法四：Java 8 流式处理（Stream API）

实现原理

利用 Java 8 的 Stream API 提供的聚合操作，通过 Collectors.groupingBy 统计元素出现次数。

代码示例

import java.util.stream.*;  
import java.util.*;  

public class DuplicateFinder {  
    public static void findDuplicatesStream(int[] arr) {  
        Map<Integer, Long> frequencyMap =  
            Arrays.stream(arr)  
                  .boxed()  
                  .collect(Collectors.groupingBy(e -> e, Collectors.counting()));  

        frequencyMap.forEach((key, value) -> {  
            if (value > 1) {  
                System.out.println("重复元素: " + key + " (出现次数: " + value + ")");  
            }  
        });  
    }  

    public static void main(String[] args) {  
        int[] example = {2, 3, 1, 2, 5, 3};  
        findDuplicatesStream(example);  
    }  
}  

输出结果

重复元素: 2 (出现次数: 2)  
重复元素: 3 (出现次数: 2)  

优缺点分析

• 优点：代码简洁，体现函数式编程思想。
• 缺点：内部实现仍需哈希表，时间复杂度 O(n)。

性能对比与场景选择

以下表格总结了四种方法的性能特征，帮助开发者根据实际需求选择最优方案：

进阶技巧：返回所有重复元素的列表

在实际开发中，可能需要返回一个包含所有重复元素的集合。以下代码演示如何改进方法二，返回 List<Integer>：

import java.util.*;  

public class DuplicateFinder {  
    public static List<Integer> findDuplicatesHashReturnList(int[] arr) {  
        HashSet<Integer> seen = new HashSet<>();  
        HashSet<Integer> duplicates = new HashSet<>();  
        for (int num : arr) {  
            if (!seen.add(num)) {  
                duplicates.add(num);  
            }  
        }  
        return new ArrayList<>(duplicates); // 转换为 List  
    }  

    public static void main(String[] args) {  
        int[] example = {2, 3, 1, 2, 5, 3};  
        List<Integer> result = findDuplicatesHashReturnList(example);  
        System.out.println("重复元素列表: " + result); // 输出: [1, 2, 3]  
    }  
}  

结论

通过本文的四种方法对比，开发者可以根据具体场景选择最适合的实现方式：

• 暴力法适合教学或数据量极小的场景。
• 哈希表法是通用的平衡方案，兼顾时间和空间效率。
• 排序法适用于允许修改数据顺序的情况。
• Stream API则为追求代码简洁性的开发者提供了一种现代化解决方案。

在实际项目中，建议优先考虑哈希表或 Stream API，同时根据内存限制和数据规模进行权衡。掌握这些技巧后，读者可以进一步探索更复杂的问题，如查找多维数组重复元素或处理对象数组的重复性判断。