Dadas dos permutaciones P1 y P2 de números de 1 a N , la tarea es encontrar el recuento máximo de los mismos elementos correspondientes en las permutaciones dadas realizando un desplazamiento cíclico hacia la izquierda o hacia la derecha en P1 .
Ejemplos:
Entrada: P1 = [5 4 3 2 1], P2 = [1 2 3 4 5]
Salida: 1
Explicación:
Tenemos un par coincidente en el índice 2 para el elemento 3.
Entrada: P1 = [1 3 5 2 4 6] , P2 = [1 5 2 4 3 6]
Salida: 3
Explicación:
el desplazamiento cíclico de la segunda permutación hacia la derecha daría 6 1 5 2 4 3, y obtenemos una coincidencia de 5, 2, 4. Por lo tanto, la respuesta es 3 parejas coincidentes.
Enfoque ingenuo: El enfoque ingenuo consiste en verificar cada cambio posible en la dirección izquierda y derecha, contar el número de pares coincidentes recorriendo todas las permutaciones formadas.
Complejidad de tiempo: O(N 2 )
Espacio auxiliar: O(1)
Enfoque eficiente: El enfoque ingenuo anterior se puede optimizar. La idea es que cada elemento almacene la menor distancia entre las posiciones de este elemento desde los lados izquierdo y derecho en arrays separadas. Por lo tanto, la solución al problema se calculará como la frecuencia máxima de un elemento de las dos arrays separadas. A continuación se muestran los pasos:
- Almacene la posición de todos los elementos de la permutación P2 en una array (digamos store[] ).
- Para cada elemento en la permutación P1 , haga lo siguiente:
- Encuentre la diferencia (digamos diff ) entre la posición del elemento actual en P2 con la posición en P1 .
- Si diff es menor que 0, actualice diff a (N – diff) .
- Almacene la frecuencia de la diferencia actual en un mapa .
- Después de los pasos anteriores, la frecuencia máxima almacenada en el mapa es el número máximo de elementos iguales después de la rotación en P1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to maximize the matching
// pairs between two permutation
// using left and right rotation
int maximumMatchingPairs(int perm1[],
int perm2[],
int n)
{
// Left array store distance of element
// from left side and right array store
// distance of element from right side
int left[n], right[n];
// Map to store index of elements
map<int, int> mp1, mp2;
for (int i = 0; i < n; i++) {
mp1[perm1[i]] = i;
}
for (int j = 0; j < n; j++) {
mp2[perm2[j]] = j;
}
for (int i = 0; i < n; i++) {
// idx1 is index of element
// in first permutation
// idx2 is index of element
// in second permutation
int idx2 = mp2[perm1[i]];
int idx1 = i;
if (idx1 == idx2) {
// If element if present on same
// index on both permutations then
// distance is zero
left[i] = 0;
right[i] = 0;
}
else if (idx1 < idx2) {
// Calculate distance from left
// and right side
left[i] = (n - (idx2 - idx1));
right[i] = (idx2 - idx1);
}
else {
// Calculate distance from left
// and right side
left[i] = (idx1 - idx2);
right[i] = (n - (idx1 - idx2));
}
}
// Maps to store frequencies of elements
// present in left and right arrays
map<int, int> freq1, freq2;
for (int i = 0; i < n; i++) {
freq1[left[i]]++;
freq2[right[i]]++;
}
int ans = 0;
for (int i = 0; i < n; i++) {
// Find maximum frequency
ans = max(ans, max(freq1[left[i]],
freq2[right[i]]));
}
// Return the result
return ans;
}
// Driver Code
int main()
{
// Given permutations P1 and P2
int P1[] = { 5, 4, 3, 2, 1 };
int P2[] = { 1, 2, 3, 4, 5 };
int n = sizeof(P1) / sizeof(P1[0]);
// Function Call
cout << maximumMatchingPairs(P1, P2, n);
return 0;
}
1
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra
¡ Consulte el artículo completo sobre Maximizar el recuento de los mismos elementos correspondientes en permutaciones dadas usando rotaciones cíclicas para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA