如何在Java中实现两个int数组的相对补集并返回int[]结果？

需求说明 #

实现一个方法，接收两个整数数组arr1和arr2，返回arr1中所有不在arr2中出现的元素组成的int[]数组。
示例：

• 输入：arr1 = {1,2,4,5,3,8}，arr2 = {0,-1,2,9,9,9,3,0,0}
• 预期输出：{1,4,5,8}

现有代码的问题 #

你提供的代码仅能打印结果，无法返回数组；且原算法依赖数组有序的前提，直接处理无序数组会得到错误结果。

解决方案 #

方案1：利用集合实现（简洁直观） #

通过HashSet存储arr2的元素，实现O(1)时间复杂度的存在性查询，遍历arr1收集符合条件的元素，最后转换为数组返回。

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

class RelativeComplement {
    static int[] relativeComplement(int[] arr1, int[] arr2) {
        // 将arr2元素存入HashSet，快速查询元素是否存在
        Set<Integer> arr2Elements = new HashSet<>();
        for (int num : arr2) {
            arr2Elements.add(num);
        }

        // 收集arr1中不在arr2里的元素
        List<Integer> resultList = new ArrayList<>();
        for (int num : arr1) {
            if (!arr2Elements.contains(num)) {
                resultList.add(num);
            }
        }

        // 将List转换为int数组返回
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 4, 5, 3, 8};
        int[] arr2 = {0, -1, 2, 9, 9, 9, 3, 0, 0};
        int[] result = relativeComplement(arr1, arr2);
        
        // 验证结果
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

特点：代码简洁，无需排序，适合中小规模数组；缺点是需要额外空间存储集合。

方案2：排序+双指针实现（低空间开销） #

先对两个数组排序，再用双指针遍历筛选元素，适合大数据量、对空间开销要求严格的场景。

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

class RelativeComplement {
    static int[] relativeComplement(int[] arr1, int[] arr2) {
        // 先对两个数组排序
        Arrays.sort(arr1);
        Arrays.sort(arr2);

        int i = 0, j = 0;
        List<Integer> resultList = new ArrayList<>();

        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) {
                // arr1当前元素不在arr2中，加入结果
                resultList.add(arr1[i]);
                // 跳过arr1中重复元素
                while (i < arr1.length - 1 && arr1[i] == arr1[i+1]) {
                    i++;
                }
                i++;
            } else if (arr1[i] > arr2[j]) {
                // arr2当前元素过小，跳过
                j++;
            } else {
                // 元素相等，跳过两个数组的当前元素
                i++;
                j++;
                // 跳过arr1重复元素
                while (i < arr1.length - 1 && arr1[i] == arr1[i-1]) {
                    i++;
                }
            }
        }

        // 处理arr1剩余的元素
        while (i < arr1.length) {
            resultList.add(arr1[i]);
            while (i < arr1.length - 1 && arr1[i] == arr1[i+1]) {
                i++;
            }
            i++;
        }

        // 转换为int数组返回
        int[] result = new int[resultList.size()];
        for (int k = 0; k < resultList.size(); k++) {
            result[k] = resultList.get(k);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 4, 5, 3, 8};
        int[] arr2 = {0, -1, 2, 9, 9, 9, 3, 0, 0};
        int[] result = relativeComplement(arr1, arr2);
        
        // 验证结果
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

特点：空间开销更低（仅需存储结果），但排序会带来O(n log n + m log m)的时间开销，适合大数据量场景。

内容的提问来源于stack exchange，提问作者Cnine