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; }
Java
// Java program for // the above approach import java.util.*; class GFG{ // Function to maximize the matching // pairs between two permutation // using left and right rotation static 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 = new int[n]; int []right = new int[n]; // Map to store index of elements HashMap<Integer, Integer> mp1 = new HashMap<>(); HashMap<Integer, Integer> mp2 = new HashMap<>(); for (int i = 0; i < n; i++) { mp1.put(perm1[i], i); } for (int j = 0; j < n; j++) { mp2.put(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.get(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 HashMap<Integer, Integer> freq1 = new HashMap<>(); HashMap<Integer, Integer> freq2 = new HashMap<>(); for (int i = 0; i < n; i++) { if(freq1.containsKey(left[i])) freq1.put(left[i], freq1.get(left[i]) + 1); else freq1.put(left[i], 1); if(freq2.containsKey(right[i])) freq2.put(right[i], freq2.get(right[i]) + 1); else freq2.put(right[i], 1); } int ans = 0; for (int i = 0; i < n; i++) { // Find maximum frequency ans = Math.max(ans, Math.max(freq1.get(left[i]), freq2.get(right[i]))); } // Return the result return ans; } // Driver Code public static void main(String[] args) { // Given permutations P1 and P2 int P1[] = {5, 4, 3, 2, 1}; int P2[] = {1, 2, 3, 4, 5}; int n = P1.length; // Function Call System.out.print(maximumMatchingPairs(P1, P2, n)); } } // This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach from collections import defaultdict # Function to maximize the matching # pairs between two permutation # using left and right rotation def maximumMatchingPairs(perm1, perm2, n): # Left array store distance of element # from left side and right array store # distance of element from right side left = [0] * n right = [0] * n # Map to store index of elements mp1 = {} mp2 = {} for i in range (n): mp1[perm1[i]] = i for j in range (n): mp2[perm2[j]] = j for i in range (n): # idx1 is index of element # in first permutation # idx2 is index of element # in second permutation idx2 = mp2[perm1[i]] 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 elif (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 freq1 = defaultdict (int) freq2 = defaultdict (int) for i in range (n): freq1[left[i]] += 1 freq2[right[i]] += 1 ans = 0 for i in range( n): # Find maximum frequency ans = max(ans, max(freq1[left[i]], freq2[right[i]])) # Return the result return ans # Driver Code if __name__ == "__main__": # Given permutations P1 and P2 P1 = [ 5, 4, 3, 2, 1 ] P2 = [ 1, 2, 3, 4, 5 ] n = len(P1) # Function Call print(maximumMatchingPairs(P1, P2, n)) # This code is contributed by chitranayal
C#
// C# program for // the above approach using System; using System.Collections.Generic; class GFG{ // Function to maximize the matching // pairs between two permutation // using left and right rotation static 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 = new int[n]; int []right = new int[n]; // Map to store index of elements Dictionary<int, int> mp1=new Dictionary<int, int>(); Dictionary<int, int> mp2=new Dictionary<int, int>(); 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 Dictionary<int, int> freq1=new Dictionary <int, int>(); Dictionary<int, int> freq2=new Dictionary <int, int>(); for (int i = 0; i < n; i++) { if(freq1.ContainsKey(left[i])) freq1[left[i]]++; else freq1[left[i]] = 1; if(freq2.ContainsKey(right[i])) freq2[right[i]]++; else freq2[right[i]] = 1; } int ans = 0; for (int i = 0; i < n; i++) { // Find maximum frequency ans = Math.Max(ans, Math.Max(freq1[left[i]], freq2[right[i]])); } // Return the result return ans; } // Driver Code public static void Main(string[] args) { // Given permutations P1 and P2 int []P1 = {5, 4, 3, 2, 1}; int []P2 = {1, 2, 3, 4, 5}; int n = P1.Length; // Function Call Console.Write(maximumMatchingPairs(P1, P2, n)); } } // This code is contributed by Rutvik_56
Javascript
<script> // Javascript program for the above approach // Function to maximize the matching // pairs between two permutation // using left and right rotation function maximumMatchingPairs(perm1, perm2, n) { // Left array store distance of element // from left side and right array store // distance of element from right side var left = Array(n); var right = Array(n); // Map to store index of elements var mp1 = new Map(), mp2 = new Map(); for (var i = 0; i < n; i++) { mp1.set(perm1[i], i); } for (var j = 0; j < n; j++) { mp2.set(perm2[j], j); } for (var i = 0; i < n; i++) { // idx1 is index of element // in first permutation // idx2 is index of element // in second permutation var idx2 = mp2.get(perm1[i]); var 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 var freq1 = new Map(), freq2 = new Map(); for (var i = 0; i < n; i++) { if(freq1.has(left[i])) freq1.set(left[i], freq1.get(left[i])+1) else freq1.set(left[i], 1) if(freq2.has(right[i])) freq2.set(right[i], freq2.get(right[i])+1) else freq2.set(right[i], 1) } var ans = 0; for (var i = 0; i < n; i++) { // Find maximum frequency ans = Math.max(ans, Math.max(freq1.get(left[i]), freq2.get(right[i]))); } // Return the result return ans; } // Driver Code // Given permutations P1 and P2 var P1 = [5, 4, 3, 2, 1]; var P2 = [1, 2, 3, 4, 5]; var n = P1.length; // Function Call document.write( maximumMatchingPairs(P1, P2, n)); </script>
1
Complejidad Temporal: O(NlogN)
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.
Publicación traducida automáticamente
Artículo escrito por durgeshkumar30508 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA