[LeetCode]Ar349. 两个数组的交集

🚩传送门：https://leetcode-cn.com/problems/intersection-of-two-arrays/

题目

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

示例 1：

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

示例 2：

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

📖 前言

本质就是查找元素

解题思路一：集合

计算两个数组的交集，直观的方法是遍历数组 nums1，对于其中的每个元素，通过遍历数组 nums2 判断该元素是否在数组 nums2 中。如果存在，则将该元素添加到返回值。

假设数组 nums1 和 nums2 的长度分别是 m 和 n，则遍历数组 nums1 需要 O(m) 的时间，判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n) 的时间，因此总时间复杂度是 **O(mn)**。

若使用哈希集合存储元素，则可以在 O(1) 的时间内判断一个元素是否在集合中，从而降低时间复杂度。

首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到 **O(m+n)**。

复杂度分析

时间复杂度：，其中 和 分别是两个数组的长度。

使用两个集合分别存储两个数组中的元素需要 的时间，遍历较小的集合并判断元素是否在另一个集合中需要 的时间，因此总时间复杂度是 。

空间复杂度：，其中 和 分别是两个数组的长度。空间复杂度主要取决于两个集合。

官方代码

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //1.定义集合
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        //2.添加元素
        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) {
        //3.获取长度较小的集合
        if (set1.size() > set2.size()) {
            return getIntersection(set2, set1);
        }
        //4.定义交集集合
        Set<Integer> intersectionSet = new HashSet<Integer>();
        //5.遍历长度较短的集合,查找其中元素是否存在于长的集合中
        for (int num : set1) {
            if (set2.contains(num)) {
                intersectionSet.add(num);
            }
        }
        //6.将集合转换成为int数组
        int[] intersection = new int[intersectionSet.size()];
        int index = 0;
        for (int num : intersectionSet) {
            intersection[index++] = num;
        }
        return intersection;
    }
}

解题思路二：排序 + 双指针

首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 pre 表示上一次加入答案数组的元素。

初始时，两个指针分别指向两个数组的头部。

1. 每次比较两个指针指向的两个数组中的数字
   • 如果两个数字不相等，则将指向较小数字的指针右移一位
   • 如果两个数字相等，且该数字不等于 pre ，将该数字添加到答案并更新 pre 变量，同时将两个指针都右移一位。
2. 当至少有一个指针超出数组范围时，遍历结束。

复杂度分析

时间复杂度：，其中 和 分别是两个数组的长度。

对两个数组排序的时间复杂度分别是 和 ，双指针寻找交集元素的时间复杂度是 ，因此总时间复杂度是 。

空间复杂度：，其中 和 分别是两个数组的长度。

空间复杂度取决于排序使用的额外空间。

官方代码

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //1.对数组进行排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, 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], 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);
    }
}

解题思路三：二分法

先将 排序，再将 中元素利用二分在 中查找是否存在

时间复杂度：，其中 和 分别是两个数组的长度。

对长度小的数组进行排序

空间复杂度：空间复杂度取决于排序使用的额外空间与两数组的交集大小。设

大小在 与 之间

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1.length<nums2.length)
            return intersection(nums2,nums1);
        //1.定义HashTable
        Set<Integer> set = new HashSet<>();
        //2.将 nums2 排序
        Arrays.sort(nums2);
        //3.检索 nums1
        for (int target : nums1) {
            //4.是二者交集且未重复
            if (binarySearch(nums2, target) && !set.contains(target)) {
                set.add(target);
            }
        }
        //5.HashTable转化数组
        int index = 0;
        int[] res = new int[set.size()];
        for (int num : set) {
            res[index++] = num;
        }
        return res;
    }
    //二分查找
    public boolean binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
            return true;
            } else if (nums[mid] > target) {
            right = mid - 1;
            } else if (nums[mid] < target) {
            left = mid + 1;
            }
        }
        return false;
    }
}