Operaciones de cola

Dados N enteros, la tarea es insertar esos elementos en la cola. Además, dados M enteros, la tarea es encontrar la frecuencia de cada número en la Cola.

Ejemplos:

Entrada: 
N = 8 
1 2 3 4 5 2 3 1 (N enteros)
M = 5
1 3 2 9 10 (M enteros)
Salida:
2 2 2 -1 -1

Explicación:
después de insertar 1, 2, 3, 4, 5, 2, 3, 1 en la cola, la frecuencia de 1 es 2, 3 es 2, 2 es 2, 9 es -1 y 10 es -1 (ya que 9 y 10 no está en la cola).

Entrada:
N = 5 
5 2 2 4 5 (N enteros)
M = 5
2 3 4 5 1 (M enteros)
Salida:
2 -1 1 2 -1

Enfoque: El problema dado se puede resolver usando una cola simple . La idea es insertar N enteros uno por uno en la cola y luego verificar la frecuencia de M enteros. Se crearán funciones separadas para realizar ambas operaciones. Siga los pasos a continuación para resolver el problema.

• Cree una cola y coloque todos los enteros dados en la cola .
• Después de colocar todos los elementos en la cola, cree otra función para contar la frecuencia de M elementos dados uno por uno.
• Tome una variable cntFrequency para realizar un seguimiento de la frecuencia del elemento actual.
• Extraiga todos los elementos de la cola hasta su tamaño y compruebe cada vez si el elemento actual en la cola es igual al elemento para el que estamos comprobando la frecuencia.
  – si ambos son iguales, incremente cntFrequency en 1
  – de lo contrario, no haga nada.
• Empuje el elemento actual de vuelta a la cola para que la cola del próximo caso no se vea perturbada.
• Imprime la frecuencia de cada elemento encontrado.

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

// Java Program to implement above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Driver code
    public static void main(String[] args)
    {
        // Declaring Queue
        Queue<Integer> q = new LinkedList<>();
        int N = 8;
        int[] a = new int[] { 1, 2, 3, 4, 5, 2, 3, 1 };
        int M = 5;
        int[] b = new int[] { 1, 3, 2, 9, 10 };
 
        // Invoking object of Geeks class
        Geeks obj = new Geeks();
 
        for (int i = 0; i < N; i++) {
            // calling insert()
            // to add elements in queue
            obj.insert(q, a[i]);
        }
 
        for (int i = 0; i < M; i++) {
            // calling findFrequency()
            int f = obj.findFrequency(q, b[i]);
            if (f != 0) {
                // variable f
                // will have final frequency
                System.out.print(f + " ");
            }
            else {
                System.out.print("-1"
                                 + " ");
            }
        }
    }
}
 
// Helper class Geeks to implement
// insert() and findFrequency()
class Geeks {
 
    // Function to insert
    // element into the queue
    static void insert(Queue<Integer> q, int k)
    {
        // adding N integers into the Queue
        q.add(k);
    }
 
    // Function to find frequency of an element
    // return the frequency of k
    static int findFrequency(Queue<Integer> q, int k)
    {
        // to count frequency of elements
        int cntFrequency = 0;
 
        // storing size of queue in a variable
        int size = q.size();
 
        // running loop until size becomes zero
        while (size-- != 0) {
 
            // storing and deleting
            // first element from queue
            int x = q.poll();
 
            // comparing if it's equal to integer K
            // that belongs to M
            if (x == k) {
                // increment count
                cntFrequency++;
            }
            // add element back to queue because
            // we also want N integers
            q.add(x);
        }
        // return the count
        return cntFrequency;
    }
}

# Python Program to implement above approach
import collections
 
# Helper class Geeks to implement
# insert() and findFrequency()
class Geeks:
 
    # Function to insert
    # element into the queue
    def insert(self, q, k):
       
        # adding N integers into the Queue
        q.append(k)
 
    # Function to find frequency of an element
    # return the frequency of k
    def findFrequency(self, q, k):
       
        # to count frequency of elements
        cntFrequency = 0
 
        # storing size of queue in a variable
        size = len(q)
 
        # running loop until size becomes zero
        while (size):
            size = size - 1
             
            # storing and deleting
            # first element from queue
            x = q.popleft()
 
            # comparing if it's equal to integer K
            # that belongs to M
            if (x == k):
               
                # increment count
                cntFrequency += 1
                 
            # add element back to queue because
            # we also want N integers
            q.append(x)
 
        # return the count
        return cntFrequency
 
# Declaring Queue
q = collections.deque()
N = 8
a = [1, 2, 3, 4, 5, 2, 3, 1]
M = 5
b = [1, 3, 2, 9, 10]
 
# Invoking object of Geeks class
obj = Geeks()
 
for i in range(N):
 
    # calling insert()
    # to add elements in queue
    obj.insert(q, a[i])
 
for i in range(M):
 
    # calling findFrequency()
    f = obj.findFrequency(q, b[i])
    if (f != 0):
       
        # variable f
        # will have final frequency
        print(f, end=" ")
    else:
        print("-1", end=" ")
print(" ")
 
# This code is contributed by gfgking.

// C# Program to implement above approach
using System;
using System.Collections.Generic;
 
public class GFG {
   
  // Helper class Geeks to implement
// insert() and findFrequency()
public class Geeks {
 
    // Function to insert
    // element into the queue
   public void insert(Queue<int> q, int k)
    {
        // adding N integers into the Queue
        q.Enqueue(k);
    }
 
    // Function to find frequency of an element
    // return the frequency of k
    public int findFrequency(Queue<int> q, int k)
    {
        // to count frequency of elements
        int cntFrequency = 0;
 
        // storing size of queue in a variable
        int size = q.Count;
 
        // running loop until size becomes zero
        while (size-- != 0) {
 
            // storing and deleting
            // first element from queue
            int x = q.Peek();
            q.Dequeue();
 
            // comparing if it's equal to integer K
            // that belongs to M
            if (x == k) {
                // increment count
                cntFrequency++;
            }
            // add element back to queue because
            // we also want N integers
            q.Enqueue(x);
        }
        // return the count
        return cntFrequency;
    }
}
 
    // Driver code
    public static void Main()
    {
       
        // Declaring Queue
        Queue<int> q = new Queue<int>();
        int N = 8;
        int[] a = new int[] { 1, 2, 3, 4, 5, 2, 3, 1 };
        int M = 5;
        int[] b = new int[] { 1, 3, 2, 9, 10 };
 
        // Invoking object of Geeks class
        Geeks obj = new Geeks();
 
        for (int i = 0; i < N; i++)
        {
           
            // calling insert()
            // to add elements in queue
            obj.insert(q, a[i]);
        }
 
        for (int i = 0; i < M; i++)
        {
           
            // calling findFrequency()
            int f = obj.findFrequency(q, b[i]);
            if (f != 0)
            {
               
                // variable f
                // will have final frequency
                Console.Write(f + " ");
            }
            else {
                Console.Write("-1"
                                 + " ");
            }
        }
    }
}
 
// This code is contributed by SURENDRA_GANGWAR.

2 2 2 -1 -1 

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