Reemplace todas las apariciones de X por Y para consultas Q en una array dada

Dada una array arr[] y una consulta de array 2D [][] que consta de consultas. Para cada consulta q , reemplace todas las ocurrencias de query[i][0] en arr[] , con query[i][1] .

Ejemplos:

Entrada: arr[] = {2, 2, 5, 1} consulta = {{2, 4}, {5, 2}}
Salida: {4, 4, 2, 1}
Explicación: Las siguientes son las operaciones realizadas en el array dada de acuerdo con las consultas dadas.
Para la primera consulta {2, 4}, reemplace todas las ocurrencias de 2 en arr[] con 4. arr[] se actualizará como arr[] = {4, 4, 5, 1}. 
Para la segunda consulta {5, 2}, reemplace todas las apariciones de 5 con 2. arr[] se actualizará como arr[] = {4, 4, 2, 1}.

Entrada: arr[] ={2, 2, 5}, consulta = {{4, 5}, {2, 5}, {1, 3}, {2, 4}}
Salida: {5, 5, 5}

Enfoque ingenuo: (solución de fuerza bruta) El enfoque ingenuo sería iterar a través de todas las consultas de query y, para cada consulta[i][0] , encontrar todas sus ocurrencias en arr[] y reemplazarlas con query[i ][1] . 

Complejidad de tiempo: O(N*Q), donde N es el tamaño de arr[] y Q es el tamaño de query[][]. 
Espacio Auxiliar: O(1)

Enfoque eficiente: una mejor solución sería usar un Hashmap, que almacena índices del elemento en la array. Siga los pasos a continuación para resolver el problema dado. 

• Inicialice un hashmap = {} y rellénelo con un elemento de array como clave y una lista que indique su posición en la array.
• Iterar a través de cada consulta q de query[][] .
  • Si q[0] está presente en el hashmap ,
    • Si q[1] está presente en el hashmap , extienda el valor de q[0] al valor de la tecla q[1] .
    • De lo contrario, agregue el valor a la tecla q[1] con el valor de la tecla q[0].
    • Elimine el par clave-valor para q[0] del hashmap .
• Ahora, cree una nueva variable map = {} , a partir de los valores del hashmap .
• Intercambie los pares clave-valor, de modo que el mapa contenga pares clave-valor como índice y valor clave de hashmap.
• Usando este mapa , ahora podemos actualizar el arreglo original arr , actualizando los valores en cada posición de arr , con el valor del mapa .

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to replace all the
// occurrences of a number with
// another given number for Q queries
void update(vector<int>& A, int N, vector<vector<int> >& Q)
{
   
    // Creating a hashmap
    map<int, vector<int> > hashmap;
    for (int i = 0; i < N; ++i) {
        hashmap[A[i]].push_back(i);
    }
 
    // Iterating with q in given queries
    for (auto q : Q) {
        if (hashmap.count(q[0])) {
            if (hashmap.count(q[1]))
                hashmap[q[1]].insert(hashmap[q[1]].end(),
                                     hashmap[q[0]].begin(),
                                     hashmap[q[0]].end());
            else
                hashmap[q[1]] = hashmap[q[0]];
            hashmap.erase(q[0]);
        }
    }
 
    // Creating map to store key value pairs
    map<int, int> new_map;
    for (auto it = hashmap.begin(); it != hashmap.end();
         ++it) {
        for (auto index : it->second)
            new_map[index] = it->first;
    }
 
    // Updating the main array with final values
    for (auto it = new_map.begin(); it != new_map.end();
         ++it)
        A[it->first] = it->second;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 2, 2, 5, 1 };
    int N = arr.size();
    vector<vector<int> > query = { { 2, 4 }, { 5, 2 } };
    update(arr, N, query);
    for (int i = 0; i < N; ++i) {
        cout << arr[i] << " ";
    }
 
   return 0;
}
 
    // This code is contributed by rakeshsahni

# Python program for above approach
 
# Function to replace all the
# occurrences of a number with
# another given number for Q queries
def update(A, N, Q):
      # Creating a hashmap
    hashmap = {a:[] for a in A}
    for i in range(N):
        hashmap[A[i]].append(i)
     
    # Iterating with q in given queries
    for q in Q:
        if q[0] in hashmap:
            if q[1] in hashmap:
                hashmap[q[1]].extend(hashmap[q[0]])
            else:
                hashmap[q[1]] = hashmap[q[0]]
            del hashmap[q[0]]
 
    # Creating map to store key value pairs
    new_map = {}
    for key, value in hashmap.items():
        for index in value:
            new_map[index] = key
             
    # Updating the main array with final values
    for key in new_map.keys():
        A[key] = new_map[key]
     
# Driver Code
if __name__ == '__main__':
  arr = [2, 2, 5, 1]
  N = len(arr)
  query = [[2, 4], [5, 2]]
  update(arr, N, query)
  print(arr)

<script>
// Javascript program for above approach
 
// Function to replace all the
// occurrences of a number with
// another given number for Q queries
function update(A, N, Q)
{
 
      // Creating a hashmap
    let hashmap = new Map();
    for(let i = 0; i < N; i++){
        if(hashmap.has(A[i])){
          let temp = hashmap.get(A[i])
          temp.push(i)
          hashmap.set(A[i], temp)
        }else{
          hashmap.set(A[i], [i])
        }
 
    }
     
    // Iterating with q in given queries
    for(q of Q){
        if(hashmap.has(q[0])){
            if (hashmap.has(q[1])){
                let temp = hashmap.get(q[1]);
                 
                temp = [...temp, ...hashmap.get(q[0])]
                hashmap.set(q[1], temp);
            }
            else{
                hashmap.set(q[1], hashmap.get(q[0]))
            }
            hashmap.delete(q[0])
        }
    }
 
    // Creating map to store key value pairs
    let new_map = new Map()
    for(x of hashmap)
        for(index of x[1])
            new_map.set(index, x[0])
             
    // Updating the main array with final values
    for(key of new_map.keys())
        A[key] = new_map.get(key)
    document.write(`[ ${A}] `)
}
     
// Driver Code
let arr = [2, 2, 5, 1]
let N = arr.length
let query = [[2, 4], [5, 2]]
update(arr, N, query)
 
// This code is contributed by gfgking.
</script>

[4, 4, 2, 1]

Complejidad de tiempo: O(max(N, Q)), donde N es el tamaño de arr[] y Q es el tamaño de query[][]. 
Espacio Auxiliar: O(N)