Cuente elementos del mismo valor colocados en los mismos índices de dos arrays dadas

Dadas dos arrays A[] y B[] de N elementos únicos , la tarea es encontrar el número máximo de elementos coincidentes de las dos arrays dadas. 

Los elementos de las dos arrays se emparejan si tienen el mismo valor y se pueden colocar en el mismo índice ( indexación basada en 0 ). (Por desplazamiento a la derecha o desplazamiento a la izquierda de las dos arrays).

 Ejemplos:

Entrada: A[] = { 5, 3, 7, 9, 8 }, B[] = { 8, 7, 3, 5, 9 }
Salida: 3
Explicación: Desplazar a la izquierda B[] por 1 índice modifica B[] a { 7, 3, 5, 9, 8 }.
Por lo tanto, los elementos de los índices 1, 3 y 4 coinciden. Por lo tanto, el conteo requerido es 3.

Entrada: A[] = { 9, 5, 6, 2 }, B[] = { 6, 2, 9, 5 }
Salida: 4

Enfoque ingenuo: el enfoque más simple para resolver este problema es observar que un desplazamiento a la derecha es lo mismo que el desplazamiento a la izquierda (N-1) , por lo tanto, realice solo un tipo de desplazamiento, por ejemplo, desplazamiento a la derecha. Además, realizar el desplazamiento a la derecha en A es lo mismo que realizar el desplazamiento a la izquierda B, por lo tanto, realice el desplazamiento a la derecha en solo una array, digamos en A[] . Aplique las operaciones de desplazamiento a la derecha en A mientras mantiene B como está y compare todos los valores de A y B para encontrar el número total de coincidencias y realizar un seguimiento del máximo de todos. 

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

Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de un mapa para realizar un seguimiento de la diferencia entre los índices de elementos iguales presentes en las arrays A[] y B[] . Si la diferencia resulta ser negativa, cambie A[] haciendo k( = N + diferencia) desplazamientos a la izquierda, lo que equivale a N – K desplazamientos a la derecha.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count maximum matched
// elements from the arrays A[] and B[]
int maxMatch(int A[], int B[], int M, int N)
{
      
    // Stores position of elements of
    // array A[] in the array B[]
    map<int,int> Aindex;
    
    // Keep track of difference
    // between the indices
    map<int,int> diff;
    
    // Traverse the array A[]
    for(int i = 0; i < M; i++)
    {
        Aindex[A[i]] = i ;
    }
    
    // Traverse the array B[]
    for(int i = 0; i < N; i++)
    {
          
        // If difference is negative, add N to it
        if (i - Aindex[B[i]] < 0)
        {     
            diff[M + i - Aindex[B[i]]] += 1;
        }
       
        // Keep track of the number of shifts
        // required to place elements at same indices
        else
        {
            diff[i - Aindex[B[i]]] += 1;
        }
    }
      
    // Return the max matches
    int max = 0;
    for(auto ele = diff.begin(); ele != diff.end(); ele++)
    {
        if(ele->second > max)
        {
            max = ele->second;
        }
    }
    return max;
}
 
// Driver code
int main()
{
    int A[] = { 5, 3, 7, 9, 8 };
    int B[] = { 8, 7, 3, 5, 9 };  
    int M = sizeof(A) / sizeof(A[0]);
    int N = sizeof(B) / sizeof(B[0]);
     
    // Returns the count 
    // of matched elements
    cout << maxMatch(A, B, M, N);
    return 0;
}
 
// This code is contributed by divyeshrabadiya07

// Java program for the above approach
import java.io.Console;
import java.util.HashMap;
import java.util.Map;
class GFG
{
 
  // Function to count maximum matched
  // elements from the arrays A[] and B[]
  static int maxMatch(int[] A, int[] B)
  {
 
    // Stores position of elements of
    // array A[] in the array B[]
    HashMap<Integer, Integer> Aindex = new HashMap<Integer, Integer>();
 
    // Keep track of difference
    // between the indices
    HashMap<Integer, Integer> diff = new HashMap<Integer, Integer>();
 
    // Traverse the array A[]
    for (int i = 0; i < A.length; i++)
    {
      Aindex.put(A[i], i);
    }
 
    // Traverse the array B[]
    for (int i = 0; i < B.length; i++)
    {
 
      // If difference is negative, add N to it
      if (i - Aindex.get(B[i]) < 0)
      {
        if (!diff.containsKey(A.length + i - Aindex.get(B[i])))
        {
          diff.put(A.length + i - Aindex.get(B[i]), 1);
        } else {
          diff.put(A.length + i - Aindex.get(B[i]), diff.get(A.length + i - Aindex.get(B[i])) + 1);
        }
      }
 
      // Keep track of the number of shifts
      // required to place elements at same indices
      else {
        if (!diff.containsKey(i - Aindex.get(B[i]))) {
          diff.put(i - Aindex.get(B[i]), 1);
        }
        else
        {
          diff.put(i - Aindex.get(B[i]),
                   diff.get(i - Aindex.get(B[i])) + 1);
        }
      }
    }
 
    // Return the max matches
    int max = 0;
    for (Map.Entry<Integer, Integer> ele : diff.entrySet())
    {
      if (ele.getValue() > max)
      {
        max = ele.getValue();
      }
    }
    return max;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    int[] A = { 5, 3, 7, 9, 8 };
    int[] B = { 8, 7, 3, 5, 9 };
 
    // Returns the count
    // of matched elements
    System.out.println(maxMatch(A, B));
  }
}
 
// This code is contributed by 29AjayKumar

# Python program for the above approach
 
 
# Function to count maximum matched
# elements from the arrays A[] and B[]
def maxMatch(A, B):
 
    # Stores position of elements of
    # array A[] in the array B[]
    Aindex = {}
 
    # Keep track of difference
    # between the indices
    diff = {}
 
    # Traverse the array A[]
    for i in range(len(A)):
        Aindex[A[i]] = i
 
    # Traverse the array B[]
    for i in range(len(B)):
 
        # If difference is negative, add N to it
        if i-Aindex[B[i]] < 0:
             
            if len(A)+i-Aindex[B[i]] not in diff:
                diff[len(A)+i-Aindex[B[i]]] = 1
                 
            else:
                diff[len(A)+i-Aindex[B[i]]] += 1
 
        # Keep track of the number of shifts
        # required to place elements at same indices
        else:
            if i-Aindex[B[i]] not in diff:
                diff[i-Aindex[B[i]]] = 1
            else:
                diff[i-Aindex[B[i]]] += 1
 
    # Return the max matches
    return max(diff.values())
 
 
# Driver Code
A = [5, 3, 7, 9, 8]
B = [8, 7, 3, 5, 9]
 
# Returns the count
# of matched elements
print(maxMatch(A, B))

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to count maximum matched
// elements from the arrays A[] and B[]
static int maxMatch(int[] A, int[] B)
{
     
    // Stores position of elements of
    // array A[] in the array B[]
    Dictionary<int,
               int> Aindex = new Dictionary<int,
                                            int>(); 
   
    // Keep track of difference
    // between the indices
    Dictionary<int,
               int> diff = new Dictionary<int,
                                          int>(); 
   
    // Traverse the array A[]
    for(int i = 0; i < A.Length; i++)
    {
        Aindex[A[i]] = i ;
    }
   
    // Traverse the array B[]
    for(int i = 0; i < B.Length; i++)
    {
         
        // If difference is negative, add N to it
        if (i - Aindex[B[i]] < 0)
        {     
            if (!diff.ContainsKey(A.Length + i -
                                  Aindex[B[i]]))
            {
                diff[A.Length + i - Aindex[B[i]]] = 1;
            }     
            else
            {
                diff[A.Length + i - Aindex[B[i]]] += 1;
            }
        }
         
        // Keep track of the number of shifts
        // required to place elements at same indices
        else
        {
            if (!diff.ContainsKey(i - Aindex[B[i]]))
            {
                diff[i - Aindex[B[i]]] = 1;
            }
            else
            {
                diff[i - Aindex[B[i]]] += 1;
            }
        }
    }
     
    // Return the max matches
    int max = 0;
    foreach(KeyValuePair<int, int> ele in diff)
    {
        if (ele.Value > max)
        {
            max = ele.Value;
        }
    }
    return max;
}
 
// Driver Code   
static void Main()
{
    int[] A = { 5, 3, 7, 9, 8 };
    int[] B = { 8, 7, 3, 5, 9 };
       
    // Returns the count 
    // of matched elements
    Console.WriteLine(maxMatch(A, B));
}
}
 
// This code is contributed by divyesh072019

<script>
      // JavaScript program for the above approach
      // Function to count maximum matched
      // elements from the arrays A[] and B[]
      function maxMatch(A, B) {
        // Stores position of elements of
        // array A[] in the array B[]
        var Aindex = {};
 
        // Keep track of difference
        // between the indices
        var diff = {};
 
        // Traverse the array A[]
        for (var i = 0; i < A.length; i++) {
          Aindex[A[i]] = i;
        }
 
        // Traverse the array B[]
        for (var i = 0; i < B.length; i++) {
          // If difference is negative, add N to it
          if (i - Aindex[B[i]] < 0) {
            if (!diff.hasOwnProperty(A.length + i - Aindex[B[i]])) {
              diff[A.length + i - Aindex[B[i]]] = 1;
            }
            else {
              diff[A.length + i - Aindex[B[i]]] += 1;
            }
          }
 
          // Keep track of the number of shifts
          // required to place elements at same indices
          else {
            if (!diff.hasOwnProperty(i - Aindex[B[i]])) {
              diff[i - Aindex[B[i]]] = 1;
            }
            else {
              diff[i - Aindex[B[i]]] += 1;
            }
          }
        }
 
        // Return the max matches
        var max = 0;
        for (const [key, value] of Object.entries(diff)) {
          if (value > max) {
            max = value;
          }
        }
        return max;
      }
 
      // Driver Code
      var A = [5, 3, 7, 9, 8];
      var B = [8, 7, 3, 5, 9];
 
      // Returns the count
      // of matched elements
      document.write(maxMatch(A, B));
</script>

Producción:

3

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