Combinar dos Maps of Array en un Map of Array ordenado

Dados dos mapas map1 y map2 que tienen una string como clave y arrays de enteros como valores, la tarea es fusionarlos en un mapa de modo que si una clave es común en ambos mapas, las arrays respectivas deben fusionarse.

Ejemplos :

Entrada : map1 = { («key1», {0, 1}), («key2», {0, 1}) }, map2 = { («key2», {1, 2}) };
Salida : { (key1, {0, 1}), (key2, {0, 1, 2}) }
Explicación : después de fusionar la array key1 se convertirá en {0, 1} y para key2 después de fusionar la array se convertirá en {0, 1 , 2} 

Entrada : map1 = {(“key1”, {0, 1})}, map2 = {(“key2”, {1, 2})};
Salida : {(tecla1, [0, 1]), (tecla2, [1, 2])}

Enfoque : La solución al problema se basa en el concepto de fusionar dos arreglos . Siga los pasos que se mencionan a continuación:

• Crear un mapa para almacenar los mapas combinados
• Atraviese map1 y almacene todos los pares clave-valor en map1.
• Traverse map2 y:
  • Si la clave de map2 no existe en map1, simplemente inserte este par de valores clave en map1
  • Si la clave de map2 existe en map1,
    • Tome la array de map1 y la array de map2
    • Ordenar ambas arrays y
    • Combínalos usando el enfoque mencionado en fusionar dos arrays .
• Devuelve el mapa3 al final.

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to merge arrays
vector<int> mergeArrays(vector<int>& a, vector<int>& b,
                        int n, int m)
{
    vector<int> mergedArray;
 
    // Declaring a map.
    // Using map as a inbuilt tool
    // to store elements in sorted order.
    map<int, bool> mp;
 
    // Inserting values to a map.
    for (int i = 0; i < n; i++)
        mp[a[i]] = true;
 
    for (int i = 0; i < m; i++)
        mp[b[i]] = true;
 
    // Printing keys of the map.
    for (auto i : mp)
        mergedArray.push_back(i.first);
    return mergedArray;
}
 
// Function to merge maps
map<string, vector<int> >
mergeMap(map<string, vector<int> >& map1,
         map<string, vector<int> >& map2)
{
    map<string, vector<int> > map3;
    map3.insert(map1.begin(), map1.end());
 
    for (auto itr : map2) {
        if (map3.find(itr.first) == map3.end())
            map3.insert({ itr.first, itr.second });
        else {
            auto temp_itr = map3.find(itr.first);
            vector<int> arr = mergeArrays(
                itr.second, temp_itr->second,
                itr.second.size(),
                temp_itr->second.size());
            map3[itr.first] = arr;
        }
    }
    return map3;
}
 
// Driver code
int main()
{
    map<string, vector<int> > map1, map2, map3;
    map1.insert({ "key1", { 0, 1 } });
    map1.insert({ "key2", { 0, 1 } });
    map2.insert({ "key2", { 1, 2 } });
 
    // Function call
    map3 = mergeMap(map1, map2);
 
    for (auto itr : map3) {
        cout << "\"" << itr.first << "\", { ";
        for (auto x : itr.second)
            cout << x << " ";
        cout << "}\n";
    }
    return 0;
}

<script>
    // JavaScript code to implement the approach
 
    // Function to merge arrays
    const mergeArrays = (a, b, n, m) => {
        let mergedArray = [];
 
        // Declaring a map.
        // Using map as a inbuilt tool
        // to store elements in sorted order.
        let mp = {};
 
        // Inserting values to a map.
        for (let i = 0; i < n; i++)
            mp[a[i]] = true;
 
        for (let i = 0; i < m; i++)
            mp[b[i]] = true;
 
        // Printing keys of the map.
        for (let i in mp)
            mergedArray.push(i);
        return mergedArray;
    }
 
    // Function to merge maps
    const mergeMap = (map1, map2) => {
        let map3 = {};
        for (let itm in map1) map3[itm] = map1[itm];
 
        for (let itr in map2) {
            if (!(itr in map3))
                map3[itr] = map2[itr];
            else {
                let arr = mergeArrays(map2[itr], map3[itr], map2[itr].length, map3[itr].length);
 
                map3[itr] = arr;
            }
        }
        return map3;
    }
 
    // Driver code
 
    let map1 = {}, map2 = {}, map3 = {};
 
    map1["key1"] = [0, 1];
    map1["key2"] = [0, 1];
    map2["key2"] = [1, 2];
 
    // Function call
    map3 = mergeMap(map1, map2);
 
    for (let itr in map3) {
        document.write(`"${itr}", { `);
        for (let x in map3[itr])
            document.write(`${map3[itr][x]} `);
        document.write("}<br/>");
    }
 
// This code is contributed by rakeshsahni
 
</script>

"key1", { 0 1 }
"key2", { 0 1 2 }

Complejidad de tiempo : O(N * log N + M * log M)
Espacio auxiliar : O(M + N)