Dada una array inicial, A[] y una array final B[], ambas de tamaño N que contienen números enteros del rango [1, N] , donde A[] representa el orden en que se insertaron los elementos y B[] representa el orden en que fueron eliminados, la tarea es encontrar el número de elementos en B[] que se encuentran en un índice anterior a su posición respectiva en A[] .
Ejemplos:
Entrada: A[ ] = {1, 2, 4, 3}, B[ ] = {2, 3, 4, 1}
Salida: 3
Explicación:
El elemento 2 se insertó después del 1, pero se eliminó antes del 1.
El elemento 3 se insertó después del 4, pero se eliminó antes del 4.
El elemento 4 se insertó después del 1, pero se eliminó antes del 1.
Por lo tanto, un total de 3 elementos se han movido hacia adelante.Entrada: A[ ] = {1, 2, 3, 4} B[ ] = {1, 2, 4, 3}
Salida: 1
Explicación:
El elemento 4 se insertó después del 3, pero se eliminó antes del 3.
Por lo tanto, solo 1 elemento ha avanzado.
Enfoque ingenuo: la forma más sencilla de resolver este problema es comparar la posición de cada elemento en B[] con la posición de todos los demás elementos en A[] y verificar si se insertó después de un elemento en A[] pero se eliminó antes en B[] . Si es así, entonces incremente el conteo. Finalmente, imprima el conteo total.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: un mejor enfoque para resolver este problema es mantener una cola e insertar los elementos de B[] en esta cola y también insertar todos los elementos en un conjunto desordenado . Un conjunto desordenado se utiliza para verificar de manera eficiente si un elemento en particular ya se procesó o no. Atraviese A[] y extraiga elementos de la cola hasta que el elemento actual A[i] aparezca en la parte superior de la cola, también siga incrementando el conteo y marque los elementos que aparecen en la parte superior de la cola como procesados. Finalmente, el conteo total dará la cantidad de elementos que se han movido hacia adelante en B[] .
Siga los pasos a continuación para resolver el problema:
- Mantenga una cola y un conjunto desordenado y almacene los valores de la array B[] en ambos.
- Ahora, itere sobre la array A[] .
- Si el elemento actual no está presente en el conjunto desordenado, significa que ya se eliminó.
- Inicializar una cuenta variable . Si algún i -ésimo elemento no se encuentra en la cola, elimine todos los elementos presentes en la cola antes de A[i] de la cola y el conjunto desordenado siga aumentando el conteo .
- Elimina A[i] de la cola y del conjunto desordenado.
- Finalmente, imprima el conteo total .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function returns maximum number
// of required elements
int maximumCount(int A[], int B[], int n)
{
queue<int> q;
unordered_set<int> s;
// Insert the elements of array B
// in the queue and set
for (int i = 0; i < n; i++) {
s.insert(B[i]);
q.push(B[i]);
}
// Stores the answer
int count = 0;
for (int i = 0; i < n; i++) {
// If A[i] is already processed
if (s.find(A[i]) == s.end())
continue;
// Until we find A[i] in the queue
while (!q.empty() && q.front() != A[i]) {
// Remove elements from the queue
s.erase(q.front());
q.pop();
// Increment the count
count++;
}
// Remove the current element A[i]
// from the queue and set.
if (A[i] == q.front()) {
q.pop();
s.erase(A[i]);
}
if (q.empty())
break;
}
// Return total count
cout << count << endl;
}
// Driver Code
int main()
{
int N = 4;
int A[] = { 1, 2, 3, 4 };
int B[] = { 1, 2, 4, 3 };
maximumCount(A, B, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function returns maximum number
// of required elements
static void maximumCount(int A[], int B[], int n)
{
Queue<Integer> q = new LinkedList<>();
HashSet<Integer> s = new HashSet<>();
// Insert the elements of array B
// in the queue and set
for(int i = 0; i < n; i++)
{
s.add(B[i]);
q.add(B[i]);
}
// Stores the answer
int count = 0;
for(int i = 0; i < n; i++)
{
// If A[i] is already processed
if (!s.contains(A[i]))
continue;
// Until we find A[i] in the queue
while (!q.isEmpty() && q.peek() != A[i])
{
// Remove elements from the queue
s.remove(q.peek());
q.remove();
// Increment the count
count++;
}
// Remove the current element A[i]
// from the queue and set.
if (A[i] == q.peek())
{
q.remove();
s.remove(A[i]);
}
if (q.isEmpty())
break;
}
// Return total count
System.out.print(count + "\n");
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
int A[] = { 1, 2, 3, 4 };
int B[] = { 1, 2, 4, 3 };
maximumCount(A, B, N);
}
}
// This code is contributed by princi singh
Python3
# Python3 Program to implement # the above approach import queue # Function returns maximum number # of required elements def maximumCount(A, B, n): q = queue.Queue() s = set() # Insert the elements of # array B in the queue # and set for i in range(n): s.add(B[i]) q.put(B[i]) # Stores the answer count = 0 for i in range(n): # If A[i] is already # processed if (A[i] not in s): continue # Until we find A[i] # in the queue while (q.qsize() > 0 and q.queue[0] != A[i]): # Remove elements from # the queue s.remove(q.queue[0]); q.get() # Increment the count count += 1 # Remove the current element A[i] # from the queue and set. if (A[i] == q.queue[0]): q.get() s.remove(A[i]) if (q.qsize() == 0): break # Return total count print(count) # Driver code N = 4 A = [1, 2, 3, 4] B = [1, 2, 4, 3] maximumCount(A, B, N) # This code is contributed by divyeshrabadiya07
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function returns maximum number
// of required elements
static void maximumCount(int []A, int []B, int n)
{
Queue<int> q = new Queue<int>();
HashSet<int> s = new HashSet<int>();
// Insert the elements of array B
// in the queue and set
for(int i = 0; i < n; i++)
{
s.Add(B[i]);
q.Enqueue(B[i]);
}
// Stores the answer
int count = 0;
for(int i = 0; i < n; i++)
{
// If A[i] is already processed
if (!s.Contains(A[i]))
continue;
// Until we find A[i] in the queue
while (q.Count != 0 && q.Peek() != A[i])
{
// Remove elements from the queue
s.Remove(q.Peek());
q.Dequeue();
// Increment the count
count++;
}
// Remove the current element A[i]
// from the queue and set.
if (A[i] == q.Peek())
{
q.Dequeue();
s.Remove(A[i]);
}
if (q.Count == 0)
break;
}
// Return total count
Console.Write(count + "\n");
}
// Driver Code
public static void Main(String[] args)
{
int N = 4;
int []A = { 1, 2, 3, 4 };
int []B = { 1, 2, 4, 3 };
maximumCount(A, B, N);
}
}
// This code is contributed by princi singh
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function returns maximum number
// of required elements
function maximumCount(A, B, n)
{
var q = [];
var s = new Set();
// Insert the elements of array B
// in the queue and set
for (var i = 0; i < n; i++) {
s.add(B[i]);
q.push(B[i]);
}
// Stores the answer
var count = 0;
for (var i = 0; i < n; i++) {
// If A[i] is already processed
if (s.has(A[i]))
{
// Until we find A[i] in the queue
while(q.length!=0 && q[0] != A[i]) {
// Remove elements from the queue
s.delete(q[0]);
q.shift();
// Increment the count
count++;
}
// Remove the current element A[i]
// from the queue and set.
if (A[i] == q[0]) {
q.shift();
s.delete(A[i]);
}
if (q.length==0)
break;
}
}
// Return total count
document.write( count );
}
// Driver Code
var N = 4;
var A = [1, 2, 3, 4];
var B = [1, 2, 4, 3];
maximumCount(A, B, N);
</script>
1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vashisthamadhur2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA