Java 中两个排序数组的并集和交集

2025年3月21日 | 阅读 9 分钟

两个有序数组的并集和交集是计算机科学和数据分析中的基本操作。在 Java 中，可以通过利用两个有序数组固有的顺序来高效地执行这些操作。两个数组的并集是两个数组中所有元素的集合，而交集是两个数组共有的所有元素的集合。这些操作通常用于各种应用，包括数据库管理、信息检索和统计。

并集

在 Java 中，可以通过合并两个数组并删除重复项来获得两个有序数组的并集。这是编程中常见的操作，通常用于合并两个列表或查找两个列表之间的公共元素等任务。并集操作将两个数组的元素合并到一个新数组中，该数组包含来自两个数组的所有唯一元素。

给定两个有序数组，找出它们的并集和交集。

示例 1

输入

arr1[] = {2, 5, 6}

arr2[] = {4, 6, 8, 10}

输出

并集：{2, 4, 5, 6, 8, 10}

交集：{6}

示例 2

输入

arr1[] = {2, 3, 6, 7, 9}

arr2[] = {1, 3, 5, 6, 8}

输出

并集：{1, 2, 3, 5, 6, 7, 8, 9}

交集：{3, 6}

示例 3

输入

arr1[] = {4, 6, 8, 10}

arr2[] = {1, 2, 4, 5, 8}

输出

并集：{1, 2, 4, 5, 6, 8, 10}

交集：{4, 8}

方法：数组 arr1[] 和 arr2[] 的并集

两个数组 arr1[] 和 arr2[] 的并集是一个新数组，其中包含来自两个数组的所有不重复元素。要获得两个有序数组的并集，我们可以使用双指针方法遍历数组并将元素添加到并集数组中。

算法

创建一个空的 ArrayList 来存储结果。
分别初始化两个指针 i 和 j，指向 arr1 和 arr2 的开头。
迭代直到指针 i 和 j 小于它们各自的数组长度。
如果 arr1[i] 小于 arr2[j]，则将 arr1[i] 添加到结果 ArrayList 中，并递增 i。
如果 arr1[i] 大于 arr2[j]，则将 arr2[j] 添加到结果 ArrayList 中，并递增 j。
如果 arr1[i] 等于 arr2[j]，则将 arr1[i] 添加到结果 ArrayList 中，并同时递增 i 和 j。
如果 arr1 或 arr2 中仍有剩余元素，则将它们添加到结果 ArrayList 中。
将结果 ArrayList 转换为整数数组并返回 i

实施

文件名：ArrayUnion.java

public class ArrayUnion {
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};
        
        int m = arr1.length;
        int n = arr2.length;
        
        System.out.print("Union of two arrays: ");
        printUnion(arr1, arr2, m, n);
    }
    
    public static void printUnion(int[] arr1, int[] arr2, int m, int n) {
        int i = 0, j = 0;
        
        //Loop through both arrays until one of them is exhausted
        while (i < m && j < n) {
            if (arr1[i] < arr2[j]) {
                // If the element at i is smaller, print it and move to the next element in arr1
                System.out.print(arr1[i++] + " ");
            } else if (arr1[i] > arr2[j]) {
                // If the element at j is smaller, print it and move to the next element in arr2
                System.out.print(arr2[j++] + " ");
            } else {
                // If the elements are equal, print one of them and move both pointers to the next element
                System.out.print(arr1[i++] + " ");
                j++;
            }
        }
        
        // If there are any remaining elements in arr1, print them
        while (i < m) {
            System.out.print(arr1[i++] + " ");
        }
        
        // If there are any remaining elements in arr2, print them
        while (j < n) {
            System.out.print(arr2[j++] + " ");
        }
    }
}

输出

Union of two arrays: 1 2 3 4 5 6 7 8

复杂度分析

代码的时间复杂度为 O(m+n)，其中 m 和 n 是两个输入数组的长度。这是因为迭代两个数组的 while 循环最多有 m+n 次迭代，因为每次迭代都会递增 i 或 j 指针，直到其中一个数组完全遍历。

空间复杂度也为 O(m+n)，因为使用的唯一额外空间是用于变量 i、j、m 和 n 以及打印的输出。

方法：使用 Set

使用 Set 的方法是查找两个有序数组并集的简单有效方法。通过将两个数组中的所有元素插入 Set 中，重复项会自动删除，生成的 Set 包含来自两个数组的所有唯一元素。

文件名：UnionOfSortedArrays.java

import java.util.*;

public class UnionOfSortedArrays {

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 3, 5, 7, 7, 9};
        int[] arr2 = {2, 4, 6, 8, 8, 8, 10};
        int m = arr1.length;
        int n = arr2.length;
        TreeSet<Integer> set = new TreeSet<>();

        // Add all elements of arr1 to the TreeSet
        for (int i = 0; i < m; i++) {
            set.add(arr1[i]);
        }

        // Add all elements of arr2 to the TreeSet
        for (int i = 0; i < n; i++) {
            set.add(arr2[i]);
        }

        // Traverse the TreeSet and print the elements
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
    }
}

输出

1 2 3 4 5 6 7 8 9 10

复杂度分析：给定代码的时间复杂度为 O(mlog(m) + nlog(n))，其中 m 和 n 是输入数组 arr1 和 arr2 的长度。通过将两个数组的所有元素添加到 TreeSet（使用自平衡二叉搜索树实现）中，可以提高时间复杂度。TreeSet 的 add() 操作的时间复杂度为 O(log(n))，其中 n 是 Set 的大小。

代码的空间复杂度为 O(m+n)，因为我们使用 TreeSet 来存储两个数组的唯一元素，并且 Set 的大小最多为 m+n。

方法：使用 HashMap

两个有序数组的并集可以在 Java 中使用 HashMap 来实现，以有效地存储和检索数组的元素，同时删除重复项。该方法涉及使用两个指针遍历数组，将元素添加到 HashMap，然后将 HashMap 的键作为两个数组的并集返回。

文件名：UnionOfSortedArrays.java

import java.util.HashMap;
import java.util.ArrayList;

public class UnionOfSortedArrays {

    public static ArrayList<Integer> union(int[] array1, int[] array2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> result = new ArrayList<>();
        int i = 0, j = 0;

        //Loop through the two arrays simultaneously using two pointers, i and j
        while (i < array1.length && j < array2.length) {
            // Compare the elements at array1[i] and array2[j]
            if (array1[i] == array2[j]) {
                // If they are equal, add the element to the HashMap with a frequency of 2 and increment both pointers i and j
                map.put(array1[i], 2);
                i++;
                j++;
            } else if (array1[i] < array2[j]) {
                // If array1[i] is less than array2[j], add array1[i] to the HashMap and increment i
                map.put(array1[i], 1);
                i++;
            } else {
                // If array1[i] is greater than array2[j], add array2[j] to the HashMap and increment j
                map.put(array2[j], 1);
                j++;
            }
        }

        // If there are any remaining elements in array1 or array2, add them to the HashMap
        while (i < array1.length) {
            map.put(array1[i], 1);
            i++;
        }

        while (j < array2.length) {
            map.put(array2[j], 1);
            j++;
        }

        // Return the keys of the HashMap as the union of the two arrays
        for (int key : map.keySet()) {
            result.add(key);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] array1 = {1, 3, 4, 5, 7};
        int[] array2 = {2, 3, 5, 6};
        ArrayList<Integer> union = union(array1, array2);
        System.out.println(union);
    }
}

输出

[1, 2, 3, 4, 5, 6, 7]

复杂度分析：算法的时间复杂度为 O(m+n)，其中 m 和 n 是两个输入数组的长度。将元素添加到 HashMap 和检索其键的复杂度是恒定的 O(1)，这有助于算法的整体效率，因为它只遍历两个数组一次。

算法的空间复杂度也为 O(m+n)，因为 HashMap 和 ArrayList 的大小最多为两个输入数组的总大小。数组 arr1[] 和 arr2[] 的交集

交集

交集是计算机科学中常见的集合运算，涉及查找两个集合之间的公共元素。在 Java 中，可以通过迭代一个数组的每个元素并检查它是否存在于另一个数组中来找到两个数组的交集。生成的数组将包含同时存在于两个数组中的元素。

方法：数组 arr1[] 和 arr2[] 的交集

算法

要找到两个数组 arr1 和 arr2 的交集，我们可以遵循以下步骤

分别初始化两个指针 i 和 j，指向 arr1 和 arr2 的开头。
使用双指针遍历两个数组。
- 如果 arr1[i] 等于 arr2[j]，则将该元素添加到交集列表中，并同时递增 i 和 j 指针。
- 否则，如果 arr1[i] 小于 arr2[j]，则递增 i。
- 否则，如果 arr1[i] 大于 arr2[j]，则递增 j。
返回交集列表。

实施

文件名：IntersectionOfArrays.java

// Import necessary classes
import java.util.ArrayList;
import java.util.Arrays;

// Define a class named IntersectionOfArrays
public class IntersectionOfArrays {

// Define a static method named Intersection that takes two integer arrays as input and returns an ArrayList of integers
public static ArrayList<Integer> intersection(int[] arr1, int[] arr2) {
    // Initialize an ArrayList to hold the Intersection of the two arrays
    ArrayList<Integer> result = new ArrayList<>();
    // Initialize two pointers, i and j, to the start of the two arrays
    int i = 0, j = 0;

    //Loop through both arrays simultaneously using the pointers i and j
    while (i < arr1.length && j < arr2.length) {
        // Compare the elements at indices i and j of the two arrays
        if (arr1[i] == arr2[j]) {
            // If they are equal, add the element to the result ArrayList, and increment both pointers i and j
            result.add(arr1[i]);
            i++;
            j++;
        } else if (arr1[i] < arr2[j]) {
            // If the element at index i of arr1 is less than the element at index j of arr2, increment i
            i++;
        } else {
            // If the element at index j of arr2 is less than the element at index i of arr1, increment j
            j++;
        }
    }

    // Return the resulting ArrayList containing the Intersection of the two input arrays
    return result;
}

// Define the main Method to test the intersection method
public static void main(String[] args) {
    int[] arr1 = {1, 2, 3, 4, 5};
    int[] arr2 = {3, 4, 5, 6, 7};
    ArrayList<Integer> intersection = intersection(arr1, arr2);
    System.out.println(intersection);
}
}

输出

[3, 4, 5]

复杂度分析：程序的 time complexity 为 O(m + n)，程序的 space complexity 为 O(min(m, n)。

方法：使用 Tree Set

此方法的主要目标是创建一个使用 tree set 的数据结构，该数据结构可以包含在 arri[] 中找到的所有不重复元素。然后将 arr2[] 的元素与 tree set 进行比较，并检查是否将其视为交集以避免重复。

文件名：TreeSetDemo.java

import java.util.*;

public class TreeSetDemo {
    
    //Method to find the Intersection of two arrays
    public static int[] findIntersection(int[] arr1, int[] arr2) {
        // create two sets to store the arrays
        Set<Integer> set1 = new TreeSet<>();
        Set<Integer> set2 = new TreeSet<>();
        // add elements of arr1 to set1
        for (int i = 0; i < arr1.length; i++) {
            set1.add(arr1[i]);
        }
        // add elements of arr2 to set2
        for (int i = 0; i < arr2.length; i++) {
            set2.add(arr2[i]);
        }
        // create a set to store the Intersection
        Set<Integer> intersectionSet = new HashSet<>(set1);
        //Retain only the elements present in both sets
        intersectionSet.retainAll(set2);
        // convert Intersection set to array and return
        int[] intersection = new int[intersectionSet.size()];
        int i = 0;
        for (int num : intersectionSet) {
            intersection[i++] = num;
        }
        return intersection;
    }
    
    public static void main(String[] args) {
        // sample input arrays
        int[] arr1 = {1, 2, 2, 3, 4, 5};
        int[] arr2 = {2, 3, 3, 4, 5, 6};
        //Call the findIntersection method and store the result in the intersection array
        int[] intersection = findIntersection(arr1, arr2);
        // print intersection array
        for (int i = 0; i < intersection.length; i++) {
            System.out.print(intersection[i] + " ");
        }
    }
}

输出

2 3 4 5

复杂度分析：findIntersection 方法的时间复杂度为 O(nlogn)，因为它涉及将 n 个元素添加到两个 TreeSet 中，这需要 O(nlogn) 的时间复杂度，然后使用 retainAll 方法查找交集，这在平均情况下需要 O(n) 的时间复杂度。

findIntersection 方法的 overall space complexity 为 O(n)，因为它涉及创建三个大小为 n 的集合，这需要 O(n) 的空间复杂度。

下一个主题Java 向量操作

Java 中两个排序数组的并集和交集

并集

方法：数组 arr1[] 和 arr2[] 的并集

方法：使用 Set

方法：使用 HashMap

交集

方法：数组 arr1[] 和 arr2[] 的交集

方法：使用 Tree Set

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中两个排序数组的并集和交集

并集

方法：数组 arr1[] 和 arr2[] 的并集

方法：使用 Set

方法：使用 HashMap

交集

方法：数组 arr1[] 和 arr2[] 的交集

方法：使用 Tree Set

相关帖子

Java 购物账单程序

Java 中链表中的下一个较大节点

Java Create Excel File

Java 中的矩阵中查找最大矩形

如何在 Java 中检查整数是否存在于某个范围内

Java 中的 HttpEntity

Java 中的 Stream mapToDouble() 方法及示例

Java 中的找不到符号错误

如何在 Java 中返回二维数组

Trapping Rain Water Problem in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器