Leetcode 两个数组的交集 II

地址：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. 对内存的分配还不太清楚