Leetcode-350-两个数组的交集 II

题目描述

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

示例 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 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

方法一：排序+双指针

算法分析：

• 首先对两个数组nums1 和 nums2进行排序

• 初始化指针i,j 用于指向两个数组

  • 指针i 指向 nums1,指针j 指向nums2
  • 如果nums1[i] < nums2[j] 则 i++
  • 如果nums1[i] > nums2[j] 则 j++
  • 如果nums1[i] == nums2[j] 则将元素拷贝到nums1[k],且同时i++ , j ++ , k++

• 初始化指针k 用于记录是否应该修改元素（作用是为了不使用额外的空间）

• 最后返回nums1的前k个元素就好

// 1. 排序
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {

        // 对两个数组进行排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i = 0;  // 指向nums1
        int j = 0;  // 指向nums2
        int k = 0;  // 用于记录nums1 和 nums2 中重复元素的个数

        while (i < nums1.length && j < nums2.length){
            if (nums1[i] < nums2[j]){
                i++;
            }else if (nums1[i] > nums2[j]){
                j++;
            }else {
                nums1[k] = nums1[i];
                i++;
                j++;
                k++;
            }
        }
        // 将一个原始的数组original，从下标from开始复制，复制到上标to，生成一个新的数组。
        // 注意这里包括下标from，不包括上标to。
        return Arrays.copyOfRange(nums1,0,k);
    }
}

复杂度分析

• 时间复杂度：O(nlogn+mlogm)其中 n，m分别代表了数组的大小。我们对数组进行了排序然后进行了线性扫描。
• 空间复杂度：O（1） 没有使用额外的空间。

方法二：哈希表

• 相对于上一题我们使用set去重，本题不要求去重，那么使用哈希表也很合适
• 如果 nums1 元素个数大于 nums2，则交换数组元素。
• 对于 nums1 的每个元素，添加到 HashMap m 中，如果元素已经存在则增加对应的计数。(这里用了一个getOrDefault方法，作用同map用if-else存放元素)
• 遍历数组nums2
  • 检查元素在map中是否存在，如果存在且个数大于0
    • 将元素拷贝到nums1[k], k++
    • 减少map中对应元素的个数

• 最后返回nums1的前k个元素。

// 2. 哈希表
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {

        // 1. 首先决定用长度小的数组进行操作（检查数组的大小并对较小的数组进行哈希映射是一个小细节，当其中一个数组较大时，会减少内存的使用。）
        if (nums1.length > nums2.length){
            return intersect(nums2,nums1);
        }

        // 2. 使用map存放元素
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n : nums1) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        // 3. 对应nums2去减少元素，（避免再开一个map浪费空间）
        int k = 0;
        for (int i = 0; i < nums2.length; i++) {
            // 如果有这个Key存在的话
            if (map.containsKey(nums2[i])){
                // 获取这个key对应的value，
                // 如果对应的value > 0,并将这个value值 - 1
                int count = map.get(nums2[i]);
                if (count > 0){
                    map.put(nums2[i],count - 1);
                    // 同时把当前元素的值赋值给nums1[k] ，这样减少了内存的浪费
                    nums1[k] = nums2[i];
                    k++;
                }
            }
        }
        return Arrays.copyOfRange(nums1,0,k);
    }
}

• 时间复杂度：O( n + m ) 其中 n，m 分别代表了数组的大小。

• 空间复杂度：O(min(m,n)) 创建了两个数组中最小大小的map映射。

打赏