День 26: Пересечение двух массивов с использованием unordered_map

Вначале я использовал два unordered_map:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        
        vector<int> res;
        std::unordered_map<int, int> mp1, mp2;
        
        for (int n1 : nums1) {
            mp1[n1]++;
        }
        
        for (int n2 : nums2) {
            mp2[n2]++;
        }
        
        for (auto element : mp1){
            if (mp2.count(element.first))
                res.push_back(element.first);
        }
        
        return res;
    }
};

Затем я упростил свой код, просто используя один контейнер unordered_map:

vector<int> res;
        std::unordered_map<int, int> mp1, mp2;
        
        for (int n1 : nums1) {
            mp1[n1]++;
        }
        
        for (auto elem : nums2){
            if (mp1.count(elem)) {
                res.push_back(elem);
                mp1.erase(elem);
            }     
        }
        
        return res;

У меня есть фантастическая страсть к использованию unordered_map без всякой причины ... Но рекомендуется использовать карту, когда размер ввода довольно мал, что даст вам log(n) время с точки зрения поиска, удаления и вставки. Когда вы рассматриваете возможность использования unordered_map, это дает вам O(1) время с точки зрения поиска, удаления и инертности; однако у него все еще есть константа k, которая увеличивает сложность. Это не означает экономии средств, когда у вас есть небольшой набор входных данных в контейнере unordered_map.