户外编程被蚊咬|如何找到两个数字串的交集呢？

照例来段碎碎念：

时隔8天，即将结束回家家度假生活的我，又拾起了电脑。在家里宽敞的户外，同时用着简书和Leetcode，不远处能看到Little Dog，虽然随着日落，突然出现了可恶的蚊子，我依然想坚持在户外记录下美好的下午。

今天的问题是：如何找到两个数字串的交集呢？

350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2's size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

我的解法

先把两个数字串排序，我用了自带的sort函数。
模拟我们人手动找相同数字的步骤，找到相同的数字就输出。
12ms的速度，不是最优。

但我这个先排序的方法，对于“大数据”就无能为力了，在下能力还不会解决存不下时的情况。

---

巨坑，吃一堑长一智

刷题的最大乐趣，其实莫过于解决各种奇葩的错误。每每叹气曰：“真是奇了怪了”。比如本题中我的这句声明：
vector<int> tmp = nums1;
之前用vector<int>& tmp;定义的tmp，一直导致nums2序列错误=。=
一个‘&’符号是导致本质巨大差距的，我本知指针和地址的奇妙原理，却在使用的时候忽略了它。导致这道题刷了好久。

---

贴上我写的不是最佳速度的AC代码：

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end() );
        sort(nums2.begin(), nums2.end() );
        vector<int> ans ;
        
        if(nums1.size() > nums2.size()  ){ 
            vector<int> tmp = nums1; //之前用vector<int>& tmp定义的，一直导致nums2序列错误=。=
            nums1 = nums2;
            nums2 = tmp;
        }
        int j = 0;
        for(int i = 0; i < nums1.size(); i++ ){//前面保证1是较小的。
            //cout<<i<<':'<<nums1[i]<<';'<<j<<':'<<nums2[j]<<endl;
            if(j >= nums2.size())
                break;
            if(nums1[i] == nums2[j]){
               ans.push_back ( nums1[i] ); //加入这个数
               j++;
            }else if (nums1[i] > nums2[j]){ //如果1比2的当前数字大，需要挪动2，1不动。
                j++;
                i--;
            }
            
        }
        return ans;
    }
};

实际上，曾经类似的题目，我用相同的方法解决过。

349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
Each element in the result must be unique.
The result can be in any order.

我的解法

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //先将两个容器升序排序
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        //声明2个容器的指标
        int i = 0;
        int j = 0;
        int len1 = nums1.size();
        int len2 = nums2.size();
        vector<int> ans;
        
        while(i < len1 && j < len2){ //ij有任何一个到头了就结束
                
                if(nums1.at(i) == nums2.at(j)){
                    if(!ans.size() || nums1.at(i) > ans.back()){
                        //不等于ans最后一个值或ans还没有第一个值
                        ans.push_back(nums1.at(i));
                    } 
                    i++;
                    j++;
                }else if(nums1.at(i) < nums2.at(j)){
                    //1容器的值比2容器的值小，则1指标++，2指标不动。
                    i++;
                }else{
                    j++;
                }
            
        }
        return ans;
    }
};

18天之隔，写法完全不同

同样是一样的思路，同样一个我，却用了不同的写法。再一次论证：我是善变的！哈哈，还是因为我目前手法不熟练，没有形成自有的规范和套路吧。

在家安闲的刷题写简书还是很休闲有趣的，明晚回京，还是家里好。
——End——