LeetCode中两个数组的交集题解-java

题目：

350. 两个数组的交集 II

难度简单424

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

示例 1：

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

示例 2:

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

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。

\进阶\：**

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

题解

方法一：哈希表

思路：

用哈希表存放每个数字出现的数字，对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。首先遍历第一个数组，并在哈希表中记录第一个数组中每个数字以及对应出现的次数，然后遍历第二个数组，若该数字存在哈希表中，则将该数字添加到答案数组中，并减少哈希表中该数字对应的次数

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // 新建一个哈希表来存放大数组中值及其对应出现的次数
        HashMap<Integer,Integer> hashmap =  new HashMap<>();
        // 新建一个数组用来存放返回值，数组长度为较大的一个数组长度
        int[] res = new int[nums1.length > nums2.length ? nums1.length : nums2.length];
        // 将数组及其对应值出现的次数存入哈希表中
        for(int i = 0; i < nums1.length; i++){
            if(!hashmap.containsKey(nums1[i])){
                hashmap.put(nums1[i], 1);
            }else{
                hashmap.put(nums1[i], hashmap.get(nums1[i]) + 1);
            }
        }
        int m = 0;
        // 遍历另外一个数组，若存在hashmap中，将值存入返回数组res中，并将其对应值出现的次数减一
        for(int j = 0; j < nums2.length; j++){
            if(hashmap.containsKey(nums2[j])){
                if(hashmap.get(nums2[j]) > 0){
                    res[m++] = nums2[j];
                    hashmap.put(nums2[j],hashmap.get(nums2[j]) - 1);
                }else{
                    hashmap.remove(nums2[j]);
                }
            }
        }
        // 截取有值的部分返回
        return Arrays.copyOfRange(res, 0, m);
    }
}

复杂度分析

时间复杂度：O(m+n)，其中 m 和 n分别是两个数组的长度。需要遍历两个数组并对哈希表进行操作，哈希表操作的时间复杂度是 O(1)，因此总时间复杂度与两个数组的长度和呈线性关系。

空间复杂度：O(min(m,n))，其中 m和 n 分别是两个数组的长度。对较短的数组进行哈希表的操作，哈希表的大小不会超过较短的数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。

提交详情

方法一提交详情

方法二：排序

思路：

首先对两个数组进行排序，然后使用两个指针遍历两个数组。

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

// class Solution {
//     public int[] intersect(int[] nums1, int[] nums2) {
//         // 新建一个哈希表来存放大数组中值及其对应出现的次数
//         HashMap<Integer,Integer> hashmap =  new HashMap<>();
//         // 新建一个数组用来存放返回值，数组长度为较大的一个数组长度
//         int[] res = new int[nums1.length > nums2.length ? nums1.length : nums2.length];
//         // 将数组及其对应值出现的次数存入哈希表中
//         for(int i = 0; i < nums1.length; i++){
//             if(!hashmap.containsKey(nums1[i])){
//                 hashmap.put(nums1[i], 1);
//             }else{
//                 hashmap.put(nums1[i], hashmap.get(nums1[i]) + 1);
//             }
//         }
//         int m = 0;
//         // 遍历另外一个数组，若存在hashmap中，将值存入返回数组res中，并将其对应值出现的次数减一
//         for(int j = 0; j < nums2.length; j++){
//             if(hashmap.containsKey(nums2[j])){
//                 if(hashmap.get(nums2[j]) > 0){
//                     res[m++] = nums2[j];
//                     hashmap.put(nums2[j],hashmap.get(nums2[j]) - 1);
//                 }else{
//                     hashmap.remove(nums2[j]);
//                 }
//             }
//         }
//         // 截取有值的部分返回
//         return Arrays.copyOfRange(res, 0, m);
//     }
// }

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // 对两个数组进行排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        // 新建一个数组，长度为两个数组中长度较小的值
        int[] intersection = new int[Math.min(length1, length2)];
        // 新建两个指针index1 与 index2
        int index1 = 0, index2 = 0, index = 0;
        // index1与index2都在范围之内
        while (index1 < length1 && index2 < length2) {
            // 如果index1 的值小于index2的值，则将index1往后移一位
            if (nums1[index1] < nums2[index2]) {
                index1++;
            // 如果index1的值大于index2 的值，将index2往后移一位
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            // 否则将此时值赋予返回数组中，并将index1 与index2 两个下标往后移一位
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}