Dados dos arreglos A y B de la misma longitud N , llenos con una permutación de números naturales de 1 a N , la tarea es contar el número de subarreglos comunes en A y B .
Ejemplos:
Entrada: A = [1, 2, 3], B = [2, 3, 1]
Salida: 4
Explicación:
Los subarreglos comunes son [1], [2], [3], [2, 3]
Por lo tanto, total cuenta = 4
Entrada: A = [1, 2, 3, 4, 5], B = [2, 3, 1, 4, 5]
Salida: 7
Explicación:
Los subarreglos comunes son [1], [2], [ 3], [4], [5], [2, 3], [4, 5]
Por lo tanto, cuenta total = 7
Enfoque ingenuo:
la idea es generar todos los subarreglos de A y B por separado, lo que tomaría O(N 2 ) para cada arreglo. Ahora, compare todos los subarreglos de A con todos los subarreglos de B y cuente los subarreglos comunes. Tomaría O(N 4 ) .
Enfoque eficiente:
la idea es usar Hashing para resolver este problema de manera eficiente.
- Cree una array Hash H de tamaño N+1 .
- Representa todos los elementos de A por sus respectivos índices:
Element Representation A[0] 0 A[1] 1 A[2] 2 . . and so on.
3. Use la array H para almacenar esta representación, H[ A[ i ] ] = i
4. Actualice los elementos de B de acuerdo con esta nueva representación usando H, B[ i ] = H[ B[ i ] ]
5. Ahora, el arreglo A se puede representar como [0, 1, 2, ..N], así que simplemente cuente el número de subarreglos en B que tienen elementos consecutivos. Una vez que obtengamos la longitud K del subarreglo de elementos consecutivos, cuente el subarreglo total posible usando la siguiente relación:
Número total de subarreglos = ( K * ( K + 1 )) / 2
Mire este ejemplo para comprender este enfoque en detalle:
Ejemplo:
A = [4, 3, 1, 2, 5]
B = [3, 1, 2, 4, 5]
Los subarreglos comunes son [1], [2], [3], [4], [5] , [3, 1], [1, 2], [3, 1, 2] = 8
1. Representar A[i] como i, y almacenar en H como H[A[i]] = i, ahora array H del índice 1 a N es,
H = [2, 3, 1, 0, 4]
2. Actualizar B según H, B[i] = H[B[i]]
B = [1, 2, 3, 0 , 4]
3. Busque el subarreglo en B con elementos consecutivos,
el subarreglo del índice 0 al 2 es [1, 2, 3], que consta de elementos consecutivos con longitud K = 3 El
elemento en el índice 3 forma un subarreglo [0] de longitud K = 1
El elemento en el índice 4 forma un subarreglo [4] de longitud K = 1
4. Número total de subarreglos comunes =
(3*(3+1))/2 + (1*(1+1))/2 + (1*(1+1))/2 = 6 + 1 + 1 = 8
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include<bits/stdc++.h>
using namespace std;
int commonSubarrays(int *A, int *B, int N)
{
// Initialising Map for
// Index Mapping
int Map[N + 1];
// Mapping elements of A
for(int i = 0 ; i< N; i++)
Map[*(A + i)] = i;
// Modify elements of B
// according to Map
for (int i = 0; i < N; i++)
{
// Changing B[i] as
// the index of B[i] in A
*(B + i) = Map[*(B + i)];
}
// Count of common subarrays
int count = 0;
// Traversing array B
int i = 0, K;
while (i < N)
{
K = 1;
i+= 1;
// While consecutive elements
// are found, we increment K
while (i < N && B[i] == B[i - 1] + 1)
{
i += 1;
K += 1;
}
// Add number of subarrays
//with length K
// to total count
count = count + ((K) * (K + 1)) / 2;
}
return count;
}
// Driver code
int main()
{
int N = 3;
int A[] = {1, 2, 3};
int B[] = {2, 3, 1};
cout << (commonSubarrays(A, B, N))
<< endl;
N = 5;
int C[] = {1, 2, 3, 4, 5};
int D[] = {2, 3, 1, 4, 5};
cout << (commonSubarrays(C, D, N));
}
// This code is contributed by chitranayal
Java
// Java implementation of the above approach
class GFG{
static int commonSubarrays(int []A,
int []B, int N)
{
// Initialising Map for
// Index Mapping
int []Map = new int[N + 1];
// Mapping elements of A
for(int i = 0; i< N; i++)
Map[A[i]] = i;
// Modify elements of B
// according to Map
for(int i = 0; i < N; i++)
{
// Changing B[i] as
// the index of B[i] in A
B[i] = Map[B[i]];
}
// Count of common subarrays
int count = 0;
// Traversing array B
int i = 0, K;
while (i < N)
{
K = 1;
i+= 1;
// While consecutive elements
// are found, we increment K
while (i < N && B[i] == B[i - 1] + 1)
{
i += 1;
K += 1;
}
// Add number of subarrays
//with length K
// to total count
count = count + ((K) * (K + 1)) / 2;
}
return count;
}
// Driver code
public static void main(String[] args)
{
int N = 3;
int A[] = {1, 2, 3};
int B[] = {2, 3, 1};
System.out.print(commonSubarrays(A, B, N));
System.out.print("\n");
N = 5;
int C[] = {1, 2, 3, 4, 5};
int D[] = {2, 3, 1, 4, 5};
System.out.print(commonSubarrays(C, D, N));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 implementation of above approach def commonSubarrays(A, B, N): # Initialising Map for # Index Mapping Map = [0 for i in range(N + 1)] # Mapping elements of A for i in range(N): Map[A[i]]= i # Modify elements of B # according to Map for i in range(N) : # Changing B[i] as # the index of B[i] in A B[i]= Map[B[i]] # Count of common subarrays count = 0 # Traversing array B i = 0 while i<N: K = 1 i+= 1 # While consecutive elements # are found, we increment K while i<N and B[i]== B[i-1]+1: i+= 1 K+= 1 # Add number of subarrays # with length K # to total count count = count + ( (K)*(K + 1))//2 return count # Driver code N = 3 A =[1, 2, 3] B =[2, 3, 1] print(commonSubarrays(A, B, N)) N = 5 A =[1, 2, 3, 4, 5] B =[2, 3, 1, 4, 5] print(commonSubarrays(A, B, N))
C#
// C# implementation of the above approach
using System;
class GFG{
static int commonSubarrays(int []A,
int []B,
int N)
{
// Initialising Map for
// Index Mapping
int []Map = new int[N + 1];
// Mapping elements of A
for(int i = 0; i < N; i++)
Map[A[i]] = i;
// Modify elements of B
// according to Map
for(int i = 0; i < N; i++)
{
// Changing B[i] as
// the index of B[i] in A
B[i] = Map[B[i]];
}
// Count of common subarrays
int count = 0;
// Traversing array B
int a = 0, K;
while (a < N)
{
K = 1;
a += 1;
// While consecutive elements
// are found, we increment K
while (a < N && B[a] == B[a - 1] + 1)
{
a += 1;
K += 1;
}
// Add number of subarrays
//with length K
// to total count
count = count + ((K) * (K + 1)) / 2;
}
return count;
}
// Driver code
public static void Main()
{
int N = 3;
int []A = {1, 2, 3};
int []B = {2, 3, 1};
Console.Write(commonSubarrays(A, B, N));
Console.Write("\n");
N = 5;
int []C = {1, 2, 3, 4, 5};
int []D = {2, 3, 1, 4, 5};
Console.Write(commonSubarrays(C, D, N));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript implementation of the above approach
function commonSubarrays(A, B, N)
{
// Initialising Map for
// Index Mapping
let Map = Array.from({length: N+1}, (_, i) => 0);
// Mapping elements of A
for(let i = 0; i< N; i++)
Map[A[i]] = i;
// Modify elements of B
// according to Map
for(let i = 0; i < N; i++)
{
// Changing B[i] as
// the index of B[i] in A
B[i] = Map[B[i]];
}
// Count of common subarrays
let count = 0;
// Traversing array B
let i = 0, K;
while (i < N)
{
K = 1;
i+= 1;
// While consecutive elements
// are found, we increment K
while (i < N && B[i] == B[i - 1] + 1)
{
i += 1;
K += 1;
}
// Add number of subarrays
//with length K
// to total count
count = count + ((K) * (K + 1)) / 2;
}
return count;
}
// Driver Code
let N = 3;
let A = [1, 2, 3];
let B = [2, 3, 1];
document.write(commonSubarrays(A, B, N));
document.write("<br/>");
N = 5;
let C = [1, 2, 3, 4, 5];
let D = [2, 3, 1, 4, 5];
document.write(commonSubarrays(C, D, N));
// This code is contributed by target_2.
</script>
4 7
Complejidad temporal: O(N)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por pedastrian y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA