Dadas dos arrays A y B de enteros positivos, los elementos de la array B pueden asignarse a los elementos de la array A solo si ambos elementos tienen el mismo valor. La tarea es calcular las posiciones en la array A a las que se asignarán los elementos de la array B. Imprima NA si no se puede realizar el mapeo de un elemento en particular.
Nota: Para una posición solo se puede mapear un entero.
Ejemplos:
Entrada: A[] = {1, 5, 2, 4, 4, 3}, B[] = {1, 2, 5, 1}
Salida: 0 2 1 NA
B[0], B[1] y B [2] se puede asignar a A[0], A[2] y A[1] respectivamente, pero B[3] no se puede asignar a ningún elemento de A porque el único ‘1’ en A ya se ha asignadoEntrada: A[] = {2, 1, 2, 3, 3, 4, 2, 4, 1}, B[] = {1, 2, 5, 1, 2, 4, 2, 3, 2, 1 }
Salida: 1 0 NA 8 2 5 6 3 NA NA
La idea es usar una tabla hash donde las claves son elementos de A[] y los valores son índices de estos elementos. Dado que puede haber más de una ocurrencia de un elemento, usamos una lista de elementos como valores en la tabla hash.
A continuación se muestra la implementación del problema anterior:
// C++ program to map elements of an array
// to equal elements of another array
#include <bits/stdc++.h>
using namespace std;
// Function to print the mapping of elements
void printMapping(int A[], int B[], int N, int M)
{
// Create a hash table where all indexes are
// stored for a given value
unordered_map<int, list<int>> m;
for (int i=0; i<N; i++)
m[A[i]].push_back(i);
// Traverse through B[]
for (int i=0; i<M; i++)
{
// If a mapping is found, print the mapping and
// remove the index from hash table so that the
// same element of A[] is not mapped again.
if (m.find(B[i]) != m.end() && m[B[i]].size() > 0)
{
cout << m[B[i]].front() << " ";
m[B[i]].pop_front();
}
else // No mapping found
{
cout << "NA ";
}
}
}
// Driver code
int main()
{
int A[] = {2, 1, 2, 3, 3, 4, 2, 4, 1};
int N = sizeof(A) / sizeof(A[0]);
int B[] = {1, 2, 5, 1, 2, 4, 2, 3, 2, 1};
int M = sizeof(B) / sizeof(B[0]);
printMapping(A, B, N, M);
return 0;
}
1 0 NA 8 2 5 6 3 NA NA
Publicación traducida automáticamente
Artículo escrito por Kushdeep_Mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA