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>
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