350两个数组的交集

wuchangjian2021-11-15 19:36:44编程学习

我写了有点麻烦了,用了两个哈希表,实际上一个就够了,题解的两个方法是哈希表和排序+双指针,都挺有收获的

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
//自己写的, 两个哈希表,太麻烦了
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int>map1;
        unordered_map<int, int>map2;
        vector<int>ans;
        for (int i = 0; i < nums1.size(); i++) {
            auto it = map1.find(nums1[i]);
            if (it != map1.end()) {
                map1[nums1[i]]++;
            }
            else {
                map1[nums1[i]] = 1;
            }
        }
        for (int i = 0; i < nums2.size(); i++) {
            auto it = map2.find(nums2[i]);
            if (it != map2.end()) {
                map2[nums2[i]]++;
            }
            else {
                map2[nums2[i]] = 1;
            }
        }
        for (auto it2 = map2.begin(); it2 != map2.end();it2++) {
            auto it1 = map1.find(it2->first);
            if (it1 != map1.end()) {
                int min;
                if (it1->second < it2->second) {
                    min = it1->second;
                }
                else min = it2->second;
                for (int j = 0; j < min; j++) {
                    ans.push_back(it2->first);
                }
           }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};
//题解方法一,哈希表
class Solution1 {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {//处理短的,减少运行时间
            return intersect(nums2, nums1);
        }
        unordered_map <int, int> m;
        for (int num : nums1) {
            ++m[num];//可以这样写,我以前都麻烦了
        }
        vector<int> intersection;//返回值
        for (int num : nums2) {
            if (m.count(num)) {
                intersection.push_back(num);
                --m[num];//如果nums2中的数在哈希表中存在,就将哈希表中的数量减一,如果为0就清掉
                if (m[num] == 0) {
                    m.erase(num);
                }
            }
        }
        return intersection;
    }
};
//题解方法二,双指针
class Solution2 {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());//排序成有序数组
        int length1 = nums1.size(), length2 = nums2.size();
        vector<int> intersection;
        int index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            }
            else if (nums1[index1] > nums2[index2]) {
                index2++;
            }
            else {
                intersection.push_back(nums1[index1]);
                index1++;
                index2++;
            }
        }
        return intersection;
    }
};
int main() {
    Solution test;
    vector<int>nums1 = {4,9,5};
    vector<int>nums2 = {9,4,9,8,4};
    vector<int>ans = test.intersect(nums1, nums2);
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i];
    }
}

相关文章

[原创]win2003、win2008升级为win2016保留数据重装恢复数据说明

[原创]win2003、win2008升级为win2016保留数据重装恢复数据说明

请注意:本教程仅适用于我司网站管理助手预装环境以及对服务器环境有一定了解的...

笨办法学Python第十天:继续打印打印

编辑以下内容: # Here's some new strang...

java.lang.IllegalArgumentException: Invalid token limit 关于Android 11 获取通讯录闪退bug

这是关于获取手机通讯录闪退的bug,出现的问题,如果不是可以...

4-灵魂存在与否的论证(3):自由意志、濒死体验以及笛卡尔的论证(耶鲁大学公开课-哲学-死亡)

自由意志与决定论 物理主义者认为人和机器人没有区别,人类和机器人都只是物...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。