Realice consultas dadas en la cola de acuerdo con las reglas dadas

Dada una cola que consta de los primeros N números naturales y consultas Query[][] del tipo {E, X}, la tarea es realizar las consultas dadas en la cola dada de acuerdo con las siguientes reglas:

  • Si el valor de E es 1 , extraiga el elemento frontal de la cola .
  • Si el valor de E es 2 , elimine el valor X de la cola si existe.
  • Si el valor de E es 3 , busque la posición de X en la cola, si existe. De lo contrario, imprima «-1» .

Ejemplos:

Entrada: N = 5, Query[][] = {{1, 0}, {3, 3}, {2, 2}}
Salida: 2
Explicación:
Inicialmente, la cola parece { 1, 2, 3, 4, 5 }. Las siguientes son las operaciones realizadas de acuerdo con las consultas dadas: 
1ra consulta E = 1, X = 0 -> 1 aparece cambiando la cola a { 2, 3, 4, 5 }.
2ª consulta E = 3, X = 3 -> Se imprime la posición de 3. 
La tercera consulta E = 2, X = 2 -> 2 se elimina de la cola cambiando la cola a { 3, 4, 5 }.

Entrada: N = 5, Consulta[][] = {{1, 0}, {3, 1}}
Salida: -1

 

Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso y la búsqueda binaria . Siga los pasos a continuación para resolver el problema dado. 

  • Inicialice una variable, digamos countE1 como 0 para contar el número de ocurrencias del evento E1 .
  • Incremente el valor de countE1 en 1 cuando la consulta sea de tipo E1 .
  • Mantener una estructura de datos establecida que almacene los elementos que se eliminan al realizar operaciones de consulta.
  • Para la consulta de tipo 3 realizar los siguientes pasos:
    • Inicializa una variable, digamos position para almacenar la posición inicial de X .
    • Encuentre el valor de X en el conjunto para verificar si X ya se eliminó o no y si X está presente en el conjunto , la impresión -1 . De lo contrario, encuentre la posición de X .
    • Atraviese el conjunto con el iterador, dígalo y , si su valor > X , salga del bucle . De lo contrario, disminuya la posición en 1 .
    • Imprime la posición final de la tienda X en la variable de posición.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to perform all the queries
// operations on the given queue
void solve(int n, int m, int** queries)
{
    // Stores the count query of type 1
    int countE1 = 0;
    set<int> removed;
 
    for (int i = 0; i < m; i++) {
 
        // Event E1: increase countE1
        if (queries[i][0] == 1)
            ++countE1;
 
        // Event E2: add the X in set
        else if (queries[i][0] == 2)
            removed.insert(queries[i][1]);
 
        // Event E3: Find position of X
        else {
 
            // Initial position is
            // (position - countE1)
            int position = queries[i][1]
                           - countE1;
 
            // If X is already removed or
            // popped out
            if (removed.find(queries[i][1])
                    != removed.end()
                || position <= 0)
                cout << "-1\n";
 
            // Finding the position of
            // X in queue
            else {
 
                // Traverse set to decrease
                // position of X for all the
                // number removed in front
                for (int it : removed) {
 
                    if (it > queries[i][1])
                        break;
 
                    position--;
                }
 
                // Print the position of X
                cout << position << "\n";
            }
        }
    }
}
 
// Driver Code
int main()
{
    int N = 5, Q = 3;
    int** queries = new int*[Q];
    for (int i = 0; i < Q; i++) {
        queries[i] = new int[2];
    }
 
    queries[0][0] = 1;
    queries[0][1] = 0;
    queries[1][0] = 3;
    queries[1][1] = 3;
    queries[2][0] = 2;
    queries[2][1] = 2;
 
    solve(N, Q, queries);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to perform all the queries
// operations on the given queue
static void solve(int n, int m, int [][]queries)
{
   
    // Stores the count query of type 1
    int countE1 = 0;
    HashSet<Integer> removed = new HashSet<Integer>();
 
    for (int i = 0; i < m; i++) {
 
        // Event E1: increase countE1
        if (queries[i][0] == 1)
            ++countE1;
 
        // Event E2: add the X in set
        else if (queries[i][0] == 2)
            removed.add(queries[i][1]);
 
        // Event E3: Find position of X
        else {
 
            // Initial position is
            // (position - countE1)
            int position = queries[i][1]
                           - countE1;
 
            // If X is already removed or
            // popped out
            if (removed.contains(queries[i][1])
                || position <= 0)
                System.out.print("-1\n");
 
            // Finding the position of
            // X in queue
            else {
 
                // Traverse set to decrease
                // position of X for all the
                // number removed in front
                for (int it : removed) {
 
                    if (it > queries[i][1])
                        break;
 
                    position--;
                }
 
                // Print the position of X
                System.out.print(position+ "\n");
            }
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5, Q = 3;
    int [][]queries = new int[Q][2];
 
    queries[0][0] = 1;
    queries[0][1] = 0;
    queries[1][0] = 3;
    queries[1][1] = 3;
    queries[2][0] = 2;
    queries[2][1] = 2;
 
    solve(N, Q, queries);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# python program for the above approach
 
# Function to perform all the queries
# operations on the given queue
 
 
def solve(n, m, queries):
 
        # Stores the count query of type 1
    countE1 = 0
    removed = set()
 
    for i in range(0, m):
 
                # Event E1: increase countE1
        if (queries[i][0] == 1):
            countE1 += 1
 
            # Event E2: add the X in set
        elif(queries[i][0] == 2):
            removed.add(queries[i][1])
 
            # Event E3: Find position of X
        else:
 
                        # Initial position is
                        # (position - countE1)
            position = queries[i][1] - countE1
 
            # If X is already removed or
            # popped out
 
            if (queries[i][1] in removed or position <= 0):
                print("-1")
 
                # Finding the position of
                # X in queue
            else:
 
                                # Traverse set to decrease
                                # position of X for all the
                                # number removed in front
                for it in removed:
                    if (it > queries[i][1]):
                        break
 
                    position -= 1
 
                    # Print the position of X
                print(position)
 
 
# Driver Code
if __name__ == "__main__":
 
    N = 5
    Q = 3
    queries = [[0 for _ in range(2)] for _ in range(Q)]
    queries[0][0] = 1
    queries[0][1] = 0
    queries[1][0] = 3
    queries[1][1] = 3
    queries[2][0] = 2
    queries[2][1] = 2
 
    solve(N, Q, queries)
 
    # This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
 
public class GFG {
     
// Function to perform all the queries
// operations on the given queue
static void solve(int n, int m, int [,]queries)
{
   
    // Stores the count query of type 1
    int countE1 = 0;
    HashSet<int> removed = new HashSet<int>();
 
    for (int i = 0; i < m; i++) {
 
        // Event E1: increase countE1
        if (queries[i, 0] == 1)
            ++countE1;
 
        // Event E2: add the X in set
        else if (queries[i, 0] == 2)
            removed.Add(queries[i, 1]);
 
        // Event E3: Find position of X
        else {
 
            // Initial position is
            // (position - countE1)
            int position = queries[i, 1]
                           - countE1;
 
            // If X is already removed or
            // popped out
            if (removed.Contains(queries[i, 1])
                || position <= 0)
                Console.WriteLine("-1\n");
 
            // Finding the position of
            // X in queue
            else {
 
                // Traverse set to decrease
                // position of X for all the
                // number removed in front
                foreach (int it in removed) {
 
                    if (it > queries[i, 1])
                        break;
 
                    position--;
                }
 
                // Print the position of X
                Console.WriteLine(position+ "\n");
            }
        }
    }
}
 
// Driver Code
public static void Main (string[] args) {
     
    int N = 5, Q = 3;
    int [,]queries = new int[Q, 2];
 
    queries[0, 0] = 1;
    queries[0, 1] = 0;
    queries[1, 0] = 3;
    queries[1, 1] = 3;
    queries[2, 0] = 2;
    queries[2, 1] = 2;
 
    solve(N, Q, queries);
}
}
 
// This code is contributed by code_hunt.

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to perform all the queries
        // operations on the given queue
        function solve(n, m, queries)
        {
         
            // Stores the count query of type 1
            let countE1 = 0;
            let removed = new Set();
 
            for (let i = 0; i < m; i++) {
 
                // Event E1: increase countE1
                if (queries[i][0] == 1)
                    ++countE1;
 
                // Event E2: add the X in set
                else if (queries[i][0] == 2)
                    removed.add(queries[i][1]);
 
                // Event E3: Find position of X
                else {
 
                    // Initial position is
                    // (position - countE1)
                    let position = queries[i][1]
                        - countE1;
 
                    // If X is already removed or
                    // popped out
                    if (removed.has(queries[i][1])
                        != false
                        || position <= 0)
                        document.write("-1" + "<br>");
 
                    // Finding the position of
                    // X in queue
                    else {
 
                        // Traverse set to decrease
                        // position of X for all the
                        // number removed in front
                        for (let it of removed) {
 
                            if (it > queries[i][1])
                                break;
 
                            position--;
                        }
 
                        // Print the position of X
                        document.write(position + "<br>");
                    }
                }
            }
        }
 
        // Driver Code
 
        let N = 5, Q = 3;
        let queries = new Array(Q);
        for (let i = 0; i < Q; i++) {
            queries[i] = new Array(2);
        }
 
        queries[0][0] = 1;
        queries[0][1] = 0;
        queries[1][0] = 3;
        queries[1][1] = 3;
        queries[2][0] = 2;
        queries[2][1] = 2;
 
        solve(N, Q, queries);
 
// This code is contributed by Potta Lokesh
    </script>
Producción: 

2

 

Complejidad del tiempo:

  • Para consulta de tipo 1: O(1)
  • Para Consulta de tipo 2: O(log N)
  • Para consulta de tipo 3: O(N 2 log N)

Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por tewatia5355 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *