题目链接

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

思路

思路 1

转成 set 直接调用内置函数

public int[] intersection(int[] nums1, int[] nums2) {
    // boxed 的作用就是将 int类型的stream 转成了 Integer 类型的 Stream
    Set<Integer> set = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
    // 转成 intString
    return Arrays.stream(nums2).distinct().filter(set::contains).toArray();
}

不采用内置函数

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();
    for (int num : nums1) {
        set1.add(num);
    }
    for (int num : nums2) {
        set2.add(num);
    }
    return getIntersection(set1, set2);
}
public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
    // 换一下位置
    if (set1.size() > set2.size()) {
        return getIntersection(set2, set1);
    }
    // 找出交集
    Set<Integer> intersectionSet = new HashSet<>();
    for (int num : set1) {
        if (set2.contains(num)) {
            intersectionSet.add(num);
        }
    }
    // 把交集转成返回结果
    int[] intersection = new int[intersectionSet.size()];
    int index = 0;
    for (int num : intersectionSet) {
        intersection[index++] = num;
    }
    return intersection;
}

复杂度分析

思路 2

去重排序后，比较大小，如果一致则加入，否则小的那条数组指针后移，直到到一个链表末尾（去重和排序其实也是调用内置函数。。。）

public int[] intersection(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int length1 = nums1.length;
    int length2 = nums2.length;
    int[] intersection = new int[length1 + length2];
    int index = 0, index1 = 0, index2 = 0;
    while (index1 < length1 && index2 < length2) {
        int num1 = nums1[index1];
        int num2 = nums2[index2];
        // 相等，加入元素，然后同时移动
        // 否则小的移动
        if (num1 == num2) {
            // 保证加入元素的唯一性
            if (index == 0 || num1 != intersection[index - 1]) {
                intersection[index++] = num1;
            }
            index1++;
            index2++;
        } else if (num1 < num2) {
            index1++;
        } else {
            index2++;
        }
    }
    return Arrays.copyOfRange(intersection, 0, index);
}