350-两个数组的交集2.md

350 两个数组的交集 2

原题地址 参考

说明：

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

进阶:

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

解法

const intersect = function (nums1, nums2) {
    let hash = new Map();
    let res = [];

    for (let i = 0; i < nums1.length; i++) {
        if (hash.has(nums1[i])) {
            hash.set(nums1[i], hash.get(nums1[i] + 1));
        } else {
            hash.set(nums1[i], 1);
        }
    }

    for (let j = 0; j < nums2.length; j++) {
        let temp = nums2[i];
        let hashKey = hash.get(temp);
        if (hash.has(temp) {
            res.push(temp);
            if (hashKey > 1) {
                hash.set(temp, hashKey - 1);
            } else {
                hash.delete(temp);
            }
        }
    }

    return res;
}

如果给定的数组已经排好序呢

上面参考链接的解法二

在这里，我们对两个数组进行排序，并且使用两个指针在一次扫面找出公共的数字。

• 对数组 nums1 和 nums2 排序。
• 初始化指针 i，j 和 k 为 0。
• 指针 i 指向 nums1，指针 j 指向 nums2
  • 如果 nums1[i] < nums2[j]，则 i++。
  • 如果 nums1[i] > nums2[j]，则 j++。
  • 如果 nums1[i] == nums2[j]，将元素拷贝到 nums1[k]，且 i++，j++，k++。
• 返回数组 nums1 前 k 个元素。

刚开始我还不理解为什么当 nums1[i] == nums2[j]，将元素要拷贝到 nums1[k]，为什么还要使用 nums1，为什么不重新使用一个新的 nums，现在明白了，因为 i, j 在 nums1/nums2里面是没有用的，k肯定会比i小，所以在nums1[k]中设置的数不会影响之后的比较，但是设置在nums1[k]中可以减少设置新的nums，这样就可以减少内存

const intersect = (nums1, nums2) => {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);

    let i = 0, j = 0, k = 0;
    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++];
            ++j;
        }
    }

    return nums1.slice(0, k);
}

复杂度分析

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

• 空间复杂度：O(1)，我们忽略存储答案所使用的空间，因为它对算法本身并不重要。