异常教程

Java 实例 – 数组交集（建议收藏）

更新时间:

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

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

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

在 Java 编程中，数组操作是基础且高频的需求。而数组交集作为数组运算的核心场景之一，常被用于数据对比、去重分析或筛选匹配项等场景。例如，电商平台可能需要比较两个商品列表的共同商品，或学校系统需要找出两门课程的共同选课学生。本文将通过循序渐进的方式，从基础到进阶，系统讲解如何在 Java 中实现数组交集的计算，并提供多种方法对比和代码示例，帮助开发者选择最适合的解决方案。

理解数组交集：定义与数学逻辑

数组交集的数学定义

在数学中，两个集合的交集（Intersection）是指同时存在于两个集合中的元素。例如，集合 A = {1, 2, 3} 和集合 B = {2, 3, 4} 的交集为 {2, 3}。在 Java 数组的语境下，数组交集即指两个数组中共同存在的元素。

数组交集的应用场景

  • 数据去重：合并两个数据源时，找出重复项。
  • 筛选匹配项：例如，两个用户列表中同时存在的用户 ID。
  • 算法优化：在复杂问题中，通过交集缩小数据范围。

数组交集的特性

  • 无序性：交集结果通常不考虑元素的原始顺序。
  • 去重性：默认情况下，交集结果中的元素不重复（除非原始数组本身包含重复元素）。

基础实现方法：嵌套循环

原理与步骤

最直观的实现方式是使用嵌套循环遍历两个数组，逐个比较元素是否相同。具体步骤如下：

  1. 创建一个空的结果数组或列表，用于存储交集元素。
  2. 外层循环遍历第一个数组的每个元素。
  3. 内层循环遍历第二个数组，判断当前元素是否存在于第二个数组中。
  4. 若存在且未被记录，则将其添加到结果集合中。

代码示例

public static int[] findIntersection(int[] arr1, int[] arr2) {
    List<Integer> result = new ArrayList<>();
    for (int num1 : arr1) {
        for (int num2 : arr2) {
            if (num1 == num2) {
                // 避免重复添加相同元素
                if (!result.contains(num1)) {
                    result.add(num1);
                }
                break; // 找到后跳出内层循环
            }
        }
    }
    // 将 List 转换为数组返回
    int[] resArray = new int[result.size()];
    for (int i = 0; i < resArray.length; i++) {
        resArray[i] = result.get(i);
    }
    return resArray;
}

时间复杂度分析

此方法的时间复杂度为 O(n²)，其中 n 是数组的平均长度。当数组较大时（如超过 1000 个元素），效率会显著下降。

优化方法：哈希表（Hash Table）

原理与步骤

哈希表通过键值对存储数据，其查找操作的时间复杂度为 O(1)，因此可以显著提升交集计算的效率。具体步骤如下：

  1. 将第一个数组的所有元素存入哈希表（如 HashSet）。
  2. 遍历第二个数组，检查每个元素是否存在于哈希表中。
  3. 若存在，则将该元素添加到结果集合，并从哈希表中移除（避免重复计数）。

代码示例

import java.util.HashSet;
import java.util.ArrayList;
import java.util.List;

public static int[] findIntersectionWithHash(int[] arr1, int[] arr2) {
    HashSet<Integer> set = new HashSet<>();
    List<Integer> result = new ArrayList<>();
    // 将第一个数组元素存入哈希表
    for (int num : arr1) {
        set.add(num);
    }
    // 遍历第二个数组并检查交集
    for (int num : arr2) {
        if (set.contains(num)) {
            result.add(num);
            set.remove(num); // 避免重复添加
        }
    }
    // 转换为数组返回
    int[] resArray = new int[result.size()];
    for (int i = 0; i < resArray.length; i++) {
        resArray[i] = result.get(i);
    }
    return resArray;
}

时间复杂度分析

此方法的时间复杂度为 O(n)，空间复杂度为 O(n)，适用于中等规模的数据处理。

集合类解决方案：使用 ArrayList 和 retainAll

原理与步骤

Java 的 ArrayList 类提供了 retainAll 方法，其功能是保留与另一个集合的交集元素。具体步骤如下：

  1. 将两个数组分别转换为 ArrayList。
  2. 对其中一个列表调用 retainAll 方法，并传入另一个列表。
  3. 最终列表中的元素即为交集结果。

代码示例

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public static int[] findIntersectionWithList(int[] arr1, int[] arr2) {
    List<Integer> list1 = new ArrayList<>();
    for (int num : arr1) {
        list1.add(num);
    }
    List<Integer> list2 = new ArrayList<>();
    for (int num : arr2) {
        list2.add(num);
    }
    // 保留 list1 中与 list2 的交集
    list1.retainAll(list2);
    // 转换为数组返回
    int[] result = new int[list1.size()];
    for (int i = 0; i < list1.size(); i++) {
        result[i] = list1.get(i);
    }
    return result;
}

注意事项

  • retainAll 方法会修改原始列表，需确保输入列表为副本。
  • 若数组中存在重复元素，结果将保留所有匹配项，而非去重后的唯一值。

Java 8 Stream API 实现

原理与步骤

Java 8 的 Stream API 提供了更简洁的流式处理方式，通过 filter 和 distinct 等操作符实现交集计算。具体步骤如下：

  1. 将第一个数组转换为流（Stream）。
  2. 使用 filter 方法筛选出存在于第二个数组中的元素。
  3. 使用 distinct 去重（可选）。
  4. 最终通过 toArray 转换为数组。

代码示例

import java.util.Arrays;
import java.util.stream.IntStream;

public static int[] findIntersectionWithStream(int[] arr1, int[] arr2) {
    return Arrays.stream(arr1)
        .filter(num -> Arrays.stream(arr2).anyMatch(n -> n == num))
        .distinct()
        .toArray();
}

代码解释

  • Arrays.stream(arr1) 将数组转为 IntStream。
  • filter 结合 anyMatch 判断元素是否存在于第二个数组。
  • distinct 确保结果无重复元素。

时间与空间复杂度对比

以下表格总结了不同方法的性能特点：

方法名称时间复杂度空间复杂度适用场景
嵌套循环O(n²)O(1)小规模数组（n < 1000）
哈希表O(n)O(n)中等规模（n < 10,000）
ArrayList + retainAllO(n)O(n)需要保留原始顺序时
Stream APIO(n²)O(n)代码简洁性优先（小数据量）

实际案例：学生选课系统的交集分析

假设某学校有两个班级的选课记录：

  • 班级 A 的选课列表：{101, 102, 103, 104}
  • 班级 B 的选课列表：{103, 104, 105, 106}

通过哈希表方法计算交集：

int[] classA = {101, 102, 103, 104};
int[] classB = {103, 104, 105, 106};
int[] commonCourses = findIntersectionWithHash(classA, classB);
// 输出结果：[103, 104]

案例扩展

若需统计共同选课的学生人数，可直接返回结果数组的长度：

int commonCount = commonCourses.length; // 输出 2

常见问题与注意事项

1. 处理重复元素

如果数组中存在重复元素（如 {2, 2, 3}），交集结果可能需要：

  • 去重：仅保留唯一值（如 {2, 3}）。
  • 保留重复次数：例如，两个数组的交集次数取最小值。

2. 数组类型与泛型

  • 对于基本类型数组（如 int[]），需通过 Integer 包装类转换。
  • 使用泛型集合（如 List<Integer>）时，确保类型一致性。

3. 空数组的处理

在代码中需添加边界条件判断，例如：

if (arr1.length == 0 || arr2.length == 0) {
    return new int[0];
}

结论

通过本文的讲解，读者应能掌握 Java 中数组交集的多种实现方法，并根据实际场景选择最优方案。嵌套循环适合小规模数据，哈希表和集合类适用于中等规模，而 Stream API 则提供了代码简洁性的优势。在实际开发中，建议优先考虑时间和空间复杂度，同时结合代码可读性进行权衡。掌握这些方法不仅能提升编码效率，还能为更复杂的算法问题（如多数组交集、动态交集计算）打下坚实基础。

如需进一步探讨数组操作或算法优化，欢迎在评论区留言交流！

最新发布

查看更多文章