大前端

前端学习之家-大前端

350两个数组的交集

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

#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];
    }
}

发表评论:

Copyright Your WebSite.Some Rights Reserved.