Imprimir Array después de mover la primera aparición de un elemento dado para terminar en Array dado para consultas Q

Dada una array arr[] de N enteros y una array consulta[] que tiene Q enteros, la tarea es imprimir la array arr[] después de mover la primera aparición de consulta[i] al final de la array arr[] para cada i en el rango [0, Q) .

Ejemplo:

Entrada: arr[] = {1, 3, 1, 3}, consulta[] = {3, 1}
Salida: 1 3 3 1
Explicación: En la primera iteración, envíe la primera aparición de consulta[0] al final, es decir , envía la primera aparición de 3 al final. 
Por lo tanto, la array se convierte en arr[] = {1, 1, 3, 3}. 
En la segunda iteración, envíe la primera aparición de query[1] al final. 
Por lo tanto, array arr[] = {1, 3, 3, 1} que es la array requerida.

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

Enfoque: El problema dado se puede resolver usando hashing . La idea es almacenar la lista de índices de cada entero en una estructura de datos establecida y, para una operación en el entero actual, eliminar el primer índice del conjunto que representa el índice de la primera aparición del entero actual e insertar el índice de el último índice en el conjunto. A continuación se detallan los pasos a seguir:

• Cree un mapa desordenado m , almacenando el conjunto de índices para cada índice.
• Itere la array arr[] e inserte todos los índices en sus respectivos conjuntos en el mapa m .
• Itere la consulta de array [] usando una variable i y realice las siguientes operaciones:
  • Elimina el primer elemento que representa la primera aparición del conjunto m[query[i]] .
  • Inserte el índice del último elemento, es decir, N+i en el conjunto m[query[i]] .
• Imprima los elementos en orden creciente de sus índices finales, que es la respuesta requerida.

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the array after
// performing the given operations
void sendToLast(vector<int> arr,
                vector<int> query)
{
    // Stores index of present
    // integers in a set
    unordered_map<int, set<int> > m;
 
    // Loop to insert indices
    // into the given map
    for (int i = 0; i < arr.size(); i++) {
        m[arr[i]].insert(i);
    }
 
    // Loop to iterate the
    // query array
    for (int i = 0; i < query.size(); i++) {
 
        // Erase the index of current
        // element from the map
        m[query[i]].erase(*m[query[i]].begin());
 
        // Insert new location
        m[query[i]].insert(arr.size() + i);
    }
 
    // Vector of pair to store index
    // value pair
    vector<pair<int, int> > v;
 
    // Insert all index value pair
    // into the vector v
    for (auto x : m) {
        for (auto y : x.second) {
            v.push_back({ y, x.first });
        }
    }
 
    // Sort v in increasing order
    // of the index
    sort(v.begin(), v.end());
 
    // Print array
    for (int i = 0; i < v.size(); i++) {
        cout << v[i].second << " ";
    }
}
 
// Driver Code
int main()
{
    vector<int> arr{ 1, 3, 1, 3 };
    vector<int> query{ 3, 1 };
 
    sendToLast(arr, query);
    return 0;
}

# Python program for the above approach
 
# Function to print array after
# performing the given operations
def sendToLast(arr, query):
   
    # Stores index of present
    # integers in a set
    m = {}
     
    # Loop to insert indices
    # into the given map
    for i in range(len(arr)):
        if arr[i] not in m:
            m[arr[i]] = []
        m[arr[i]].append(i)
         
    # Loop to iterate the
    # query array
    for i in range(len(query)):
       
        # Erase the index of current
        # element from the map    
        m[query[i]] = m[query[i]][1:] #-.erase(*m[query[i]].begin())
         
        # Insert new location
        m[query[i]].append(len(arr) + i)
         
    # Vector of pair to store index
    # value pair
    v =[]
     
    # Insert all index value pair
    # into the vector v
    for x in m:
        for y in m[x]:
            v.append([y, x])
             
    # Sort v in increasing order
    # of the index
    v.sort()
     
    # Print array
    for i in range(len(v)):
        print(v[i][1], end = " ")
 
# Driver Code
arr =  [1, 3, 1, 3]
query = [3, 1]
 
sendToLast(arr, query)
 
# This code is contributed by Shubham Singh

1 3 3 1 

Complejidad temporal: O(Q * log N)
Espacio auxiliar: O(N)