Programa Java para maximizar el recuento de los mismos elementos correspondientes en arrays dadas por rotación

Dadas dos arrays arr1[] y arr2[] de N enteros y la array arr1[] tiene elementos distintos. La tarea es encontrar el recuento máximo de los mismos elementos correspondientes en las arrays dadas realizando un desplazamiento cíclico hacia la izquierda o hacia la derecha en la array arr1[] . 
Ejemplos: 
 

Entrada: arr1[] = { 6, 7, 3, 9, 5 }, arr2[] = { 7, 3, 9, 5, 6 } Salida: 5 Explicación: Al realizar un desplazamiento cíclico a la izquierda 
en la 
array 
arr1[] por 1
Array actualizada arr1[] = {7, 3, 9, 5, 6}  . 
Esta rotación contiene un número máximo de elementos iguales entre la array arr1[] y arr2[].
Entrada: arr1[] = {1, 3, 2, 4}, arr2[] = {4, 2, 3, 1} 
Salida: 2 
Explicación: 
Al realizar un desplazamiento cíclico a la izquierda en la array arr1[] por 1. 
Array actualizada arr1 [] = {3, 2, 4, 1} 
Esta rotación contiene un número máximo de elementos iguales entre la array arr1[] y arr2[]. 
 

Enfoque: este problema se puede resolver utilizando el enfoque codicioso . A continuación se muestran los pasos: 
 

1. Almacene la posición de todos los elementos de la array arr2[] en una array (por ejemplo, store[] ).
2. Para cada elemento de la array arr1[] , haga lo siguiente: 
   • Encuentre la diferencia (digamos diff ) entre la posición del elemento actual en arr2[] con la posición en arr1[] .
   • 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 arr1[] .

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

// Java program of the above approach
import java.util.*;
class GFG{
  
// Function that prints maximum
// equal elements
static void maximumEqual(int a[], 
                         int b[], int n)
{
  
    // Vector to store the index
    // of elements of array b
    int store[] = new int[(int) 1e5];
  
    // Storing the positions of
    // array B
    for (int i = 0; i < n; i++) 
    {
        store[b[i]] = i + 1;
    }
  
    // frequency array to keep count
    // of elements with similar
    // difference in distances
    int ans[] = new int[(int) 1e5];
  
    // Iterate through all element in arr1[]
    for (int i = 0; i < n; i++)
    {
  
        // Calculate number of
        // shift required to
        // make current element
        // equal
        int d = Math.abs(store[a[i]] - (i + 1));
  
        // If d is less than 0
        if (store[a[i]] < i + 1) 
        {
            d = n - d;
        }
  
        // Store the frequency
        // of current diff
        ans[d]++;
    }
  
    int finalans = 0;
  
    // Compute the maximum frequency
    // stored
    for (int i = 0; i < 1e5; i++)
        finalans = Math.max(finalans,
                            ans[i]);
  
    // Printing the maximum number
    // of equal elements
    System.out.print(finalans + "
");
}
  
// Driver Code
public static void main(String[] args)
{
    // Given two arrays
    int A[] = { 6, 7, 3, 9, 5 };
    int B[] = { 7, 3, 9, 5, 6 };
  
    int size = A.length;
  
    // Function Call
    maximumEqual(A, B, size);
}
}
  
// This code is contributed by sapnasingh4991

5

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

¡Consulte el artículo completo sobre Maximizar el recuento de los mismos elementos correspondientes en arrays dadas por rotación para obtener más detalles!