Java 数组交集的实现代码

下面是Java数组交集的实现代码完整攻略。

实现思路

交集是指两个集合中都存在的元素，可以用两种方法来实现数组交集。

• 嵌套循环：在第一个数组中循环遍历每个元素，在第二个数组中再循环遍历每个元素，如果两个元素相等，则为交集元素之一。
• HashSet数据结构：使用HashSet将第一个数组中的元素都添加进去，然后遍历第二个数组，在HashSet中查找是否存在相同的元素。

方法1的时间复杂度是 $O(n^2)$，而方法2的时间复杂度是 $O(n)$，因此后者更加高效。

代码实现

方法1：嵌套循环

public static int[] intersection(int[] nums1, int[] nums2) {
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j < nums2.length; j++) {
            if (nums1[i] == nums2[j] && !list.contains(nums1[i])) {
                list.add(nums1[i]);
            }
        }
    }
    int[] res = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        res[i] = list.get(i);
    }
    return res;
}

这里使用了ArrayList来存储结果，对于每个元素都进行了一次遍历，所以时间复杂度是 $O(n^2)$ 。同时，使用了contains方法来判断某个元素是否已经存在于结果列表中，这个操作也是比较耗时的。

方法2：HashSet

public static int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    for (int num : nums1) {
        set1.add(num);
    }
    Set<Integer> set2 = new HashSet<>();
    for (int num : nums2) {
        if (set1.contains(num)) {
            set2.add(num);
        }
    }
    int[] res = new int[set2.size()];
    int i = 0;
    for (int num : set2) {
        res[i++] = num;
    }
    return res;
}

这里使用了HashSet数据结构来存储数组元素，时间复杂度是 $O(n)$。

示例说明

示例1

int[] nums1 = {4, 9, 5};
int[] nums2 = {9, 4, 9, 8, 4};
System.out.println(Arrays.toString(intersection(nums1, nums2)));

以上示例中，数组 nums1 中包含元素 4 和 9，数组 nums2 中包含元素 9，4，因此它们的交集应该是 [9, 4]。

示例2

int[] nums1 = {1, 2, 2, 1};
int[] nums2 = {2, 2};
System.out.println(Arrays.toString(intersection(nums1, nums2)));

以上示例中，数组 nums1 中包含元素 1 和 2，数组 nums2 中包含元素 2，因此它们的交集应该是 [2]。

希望这些示例能够帮助你更好地理解Java数组交集的实现。