Leetcode 两个数组的交集 II

本文最后更新于:2020年11月19日 上午

地址:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/26/

一、题目

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

示例 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:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> inter;    //保存交集的数组
        for (int i = 0; i < nums1.size(); i++) {    //任选一个数组作为外层循环,选小的数组较好
            int q = 0;     //用于统计交集中有多少个与当前nums1[i]相等的数
            for (int j = 0; j < inter.size(); j++) {   //统计
                if (inter[j] == nums1[i])
                    q++;
            }
            //q>=1表明交集中已存在q个与nums1[i]相等的数
            //q==0表明交集中不存在与nums1[i]相等的数
            for (int k = 0; k < nums2.size(); k++) {    //在nums2中查找与nums1[i]相等的数
                //表明nums1[i]与nums2[k]是一对新相等的数,要插入到inter数组中
                if (q == 0 && nums2[k] == nums1[i]) {
                    inter.insert(inter.end(), nums1[i]);
                    //一旦插入一个新的相交的元素就跳出循环
                    //否则如果nums2中后序还有相等的数就会多次插入,逻辑错误
                    break;
                }
                //相当于从第q个与nums1[i]相等的数的后开始找新的与nums1[i]相等的数
                else if (nums2[k] == nums1[i])
                    q--;
            }
        }
        return inter;
    }
};

进阶思路:

  1. 如果是已经排好序的两个数组,可以不用每次都从头开始查找,每一次查找的时候记录下当前的位置,这个位置之前的已经不可能存在交集了也就不用再查找一次了
  2. 如果 nums1 的大小比 nums2 小很多,可以把nums1作为外层循环
  3. 对内存的分配还不太清楚

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!