Prerrequisito: Pila , Hashing
Dada una pila de N números y una array de números. Cuente el número de operaciones emergentes requeridas para obtener cada elemento de la array. Una vez que se abre un elemento, no se vuelve a empujar. Suponga que todos los elementos de la array presentes dentro de la pila inicialmente.
Ejemplos:
Entrada: N = 5
Pila: 6 4 3 2 1
Array: 6 3 4 1 2
Salida: 1 2 0 2 0
El primer elemento de la pila es el mismo que los elementos de la array. Entonces, para obtener 6, se requiere un pop, es decir, sacar 6 de la pila. Para obtener 3, se extraerán 2 elementos, es decir, 4 y 3. Para obtener 4, ya se extrajeron 4, por lo que no extraeremos más elementos. De manera similar, para obtener 1, extraeremos 2 elementos y para los 2, no se agregará ningún número de elementos emergentes.
Enfoque: esta pregunta se puede resolver fácilmente usando una pila. Seguiremos abriendo los elementos hasta que encontremos el elemento que estamos buscando. El único obstáculo es cómo manejar el caso cuando el elemento ya apareció y no está presente en la pila. Para eso, mantendremos un mapa hash. A medida que extraemos un elemento de la pila, insertaremos ese elemento en el mapa hash de modo que si el elemento aparece más tarde en la array, primero verificaremos si está presente dentro de los mapas hash o, en otras palabras, se ha extraído de la pila previamente. . De lo contrario, sabremos que está presente dentro de la pila y comenzaremos a extraer los elementos hasta que encontremos el número requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count
void countEle(stack<int>& s, int a[], int N)
{
// Hashmap to store all the elements
// which are popped once.
unordered_map<int, bool> mp;
for (int i = 0; i < N; ++i) {
int num = a[i];
// Check if the number is present
// in the hashmap Or in other words
// been popped out from the stack before.
if (mp.find(num) != mp.end())
cout << "0 ";
else {
int cnt = 0;
// Keep popping the elements
// while top is not equal to num
while (s.top() != num) {
mp[s.top()] = true;
s.pop();
cnt++;
}
// Pop the top ie. equal to num
s.pop();
cnt++;
// Print the number of elements popped.
cout << cnt << " ";
}
}
}
// Driver code
int main()
{
int N = 5;
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(6);
int a[] = { 6, 3, 4, 1, 2 };
countEle(s, a, N);
return 0;
}
Java
// Java program to implement above approach
import java.util.HashMap;
import java.util.Stack;
class GFG
{
// Function to find the count
public static void countEle(Stack<Integer> s,
int[] a, int N)
{
// Hashmap to store all the elements
// which are popped once.
HashMap<Integer,
Boolean> mp = new HashMap<>();
for (int i = 0; i < N; ++i)
{
int num = a[i];
// Check if the number is present
// in the hashmap Or in other words
// been popped out from the stack before.
if (mp.containsKey(num))
System.out.print("0 ");
else
{
int cnt = 0;
// Keep popping the elements
// while top is not equal to num
while (s.peek() != num)
{
mp.put(s.peek(), true);
s.pop();
cnt++;
}
// Pop the top ie. equal to num
s.pop();
cnt++;
// Print the number of elements popped.
System.out.print(cnt + " ");
}
}
}
// Driver code
public static void main(String[] args)
{
int N = 5;
Stack<Integer> s = new Stack<>();
s.add(1);
s.add(2);
s.add(3);
s.add(4);
s.add(6);
int[] a = { 6, 3, 4, 1, 2 };
countEle(s, a, N);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to implement above approach
# Function to find the count
def countEle(s, a, N):
# Hashmap to store all the elements
# which are popped once.
mp = {}
for i in range(0, N):
num = a[i]
# Check if the number is present
# in the hashmap Or in other words
# been popped out from the stack before.
if num in mp:
print("0", end = " ")
else:
cnt = 0
# Keep popping the elements
# while top is not equal to num
while s[-1] != num:
mp[s.pop()] = True
cnt += 1
# Pop the top ie. equal to num
s.pop()
cnt += 1
# Print the number of elements popped.
print(cnt, end = " ")
# Driver code
if __name__ == "__main__":
N = 5
s = []
s.append(1)
s.append(2)
s.append(3)
s.append(4)
s.append(6)
a = [6, 3, 4, 1, 2]
countEle(s, a, N)
# This code is contributed by Rituraj Jain
C#
// C# implementation of the above approach:
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the count
public static void countEle(Stack<int> s,
int[] a, int N)
{
// Hashmap to store all the elements
// which are popped once.
Dictionary<int,
bool> mp = new Dictionary<int,
bool>();
for (int i = 0; i < N; ++i)
{
int num = a[i];
// Check if the number is present
// in the hashmap Or in other words
// been popped out from the stack before.
if (mp.ContainsKey(num))
Console.Write("0 ");
else
{
int cnt = 0;
// Keep popping the elements
// while top is not equal to num
while (s.Peek() != num)
{
mp.Add(s.Peek(), true);
s.Pop();
cnt++;
}
// Pop the top ie. equal to num
s.Pop();
cnt++;
// Print the number of elements popped.
Console.Write(cnt + " ");
}
}
}
// Driver code
public static void Main(String[] args)
{
int N = 5;
Stack<int> s = new Stack<int>();
s.Push(1);
s.Push(2);
s.Push(3);
s.Push(4);
s.Push(6);
int[] a = { 6, 3, 4, 1, 2 };
countEle(s, a, N);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to implement above approach
// Function to find the count
function countEle(s, a, N)
{
// Hashmap to store all the elements
// which are popped once.
var mp = new Map();
for (var i = 0; i < N; ++i) {
var num = a[i];
// Check if the number is present
// in the hashmap Or in other words
// been popped out from the stack before.
if (mp.has(num))
document.write( "0 ");
else {
var cnt = 0;
// Keep popping the elements
// while top is not equal to num
while (s[s.length-1] != num) {
mp.set(s[s.length-1], true);
s.pop();
cnt++;
}
// Pop the top ie. equal to num
s.pop();
cnt++;
// Print the number of elements popped.
document.write( cnt + " ");
}
}
}
// Driver code
var N = 5;
var s = [];
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(6);
var a = [6, 3, 4, 1, 2 ];
countEle(s, a, N);
</script>
1 2 0 2 0
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA