Programa Java para maximizar el recuento de los mismos elementos correspondientes en permutaciones dadas usando rotaciones cíclicas

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:
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:
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:  

  1. Almacene la posición de todos los elementos de la permutación P2 en una array (digamos store[] ).
  2. 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 .
  3. 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:
 

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
Producción: 

1

 

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)

¡ 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *