Skip to content

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

Latest commit

 

History

History
124 lines (90 loc) · 3.86 KB

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

File metadata and controls

124 lines (90 loc) · 3.86 KB
Raw

350 两个数组的交集 2

原题地址 参考

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

 

示例 1：

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

示例 2:

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

 

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

 

进阶：

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

说明：

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

进阶:

如果给定的数组已经排好序呢？你将如何优化你的算法？ 如果 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)，我们忽略存储答案所使用的空间，因为它对算法本身并不重要。