Consultas para sumar, quitar y devolver la diferencia de máximo y mínimo.

Posted on by Rudeus Greyrat

Dadas las consultas Q. Las consultas son de tres tipos y se describen a continuación:  

  • Agregue el número num a la lista.
  • Elimina el número num de la lista.
  • Devuelve la diferencia entre el número máximo y mínimo de la lista.

La tarea es escribir un programa que realice las consultas anteriores.

Nota: Los números son distintos y en cada llamada de consulta-3, habrá un mínimo de 1 elemento en la lista. 

Ejemplos: 

Entrada: 
Q = 5 
Consulta de tipo 1: num = 3 
Consulta de tipo 1: num = 5 
Consulta de tipo 1: num = 6 
Consulta de tipo 2: num = 6 
Consulta de tipo 1: num = 2 
Consulta de tipo 3: 
Salida: 4
Dado que la consulta de tipo 3 se ha llamado una sola vez, la respuesta en este momento es 4. 
Después de la primera consulta de tipo 1, la lista es {3} 
Después de la segunda consulta de tipo 1, la lista es {3, 5} 
Después de la tercera consulta de tipo 1, la lista es {3, 5, 6} 
Después de la cuarta consulta de tipo 2, la lista es {3, 5} 
Después de la quinta consulta de tipo 1, la lista es {2, 3, 5} 
En la sexta consulta de tipo 3, la respuesta es 5-2. 

Una solución simple es seguir los siguientes pasos: 

  • almacenar los números en una array de vectores.
  • Para la consulta de tipo 1, agregue un elemento a la array.
  • Para una consulta de tipo 2, elimine el elemento del vector o array.
  • Para la consulta de tipo 3, recorra la array y encuentre el mínimo y el máximo en la array y devuelva la diferencia de ellos.

Complejidad de tiempo: 
consulta de tipo 1: O (1) ya que la inserción de un elemento costará O (1) tiempo.
Consulta de tipo 2: O (N) ya que en el peor de los casos necesitaríamos recorrer toda la array para buscar y eliminar el elemento.
Consulta de tipo 3: O (N) ya que necesitamos atravesar la array para encontrar el elemento mínimo y máximo. 
Espacio auxiliar: O (N), ya que necesitamos usar espacio adicional para la array.

Una solución eficiente es utilizar un árbol de búsqueda binario autoequilibrado (Implementado como contenedor de conjuntos en C++ o TreeSet en Java). Los siguientes pasos se siguen para resolver el problema anterior.  

  • Inserte el elemento en el contenedor usando la función insert() .
  • Elimine el elemento del contenedor usando la función erase() .
  • El valor mínimo estará siempre al principio y el máximo al final siempre. Se pueden recuperar utilizando las funciones begin() y rbegin() .

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

C++

// C++ program to perform Queries to
// add, remove and return
// the difference of maximum and minimum.
#include <bits/stdc++.h>
    using namespace std;
set<int> s;
 
// function to perform query 1
void performQueryOne(int num)
{
    // insert the element
    s.insert(num);
}
 
// function to perform query 2
void performQueryTwo(int num)
{
    // erase the element
    s.erase(num);
}
 
// function to perform query 3
int performQueryThree()
{
    int mini = *(s.begin());
    int maxi = *(s.rbegin());
 
    return maxi - mini;
}
 
// Driver Code
int main()
{
 
    // query type-1
    int num = 3;
    performQueryOne(num);
 
    // query type-1
    num = 5;
    performQueryOne(num);
 
    // query type-1
    num = 6;
    performQueryOne(num);
 
    // query type-2
    num = 5;
    performQueryTwo(num);
 
    // query type-1
    num = 2;
    performQueryOne(num);
 
    // query type-3
    cout << performQueryThree();
 
    return 0;
}

Java

// Java program to perform Queries
// to add, remove and return
// the difference of maximum and
// minimum using TreeSet.
import java.util.*;
class GFG
{
static SortedSet<Integer> t = new TreeSet<Integer>();
 
// function to perform query 1
static void performQueryOne(int num)
{
    // insert the element
    t.add(num);
}
 
// function to perform query 2
static void performQueryTwo(int num)
{
    // erase the element
    t.remove(num);
}
 
// function to perform query 3
static int performQueryThree()
{
    int mini = t.first();
    int maxi = t.last();
 
    return maxi - mini;
}
 
// Driver Code
public static void main(String[] args)
{
    // query type-1
    int num = 3;
    performQueryOne(num);
 
    // query type-1
    num = 5;
    performQueryOne(num);
 
    // query type-1
    num = 6;
    performQueryOne(num);
 
    // query type-2
    num = 5;
    performQueryTwo(num);
 
    // query type-1
    num = 2;
    performQueryOne(num);
 
    // query type-3
    System.out.println(performQueryThree());
}
}
 
// This code is contributed by debjitdbb

Python3

# Python3 program to perform Queries
# to add, remove and return
# difference of maximum and minimum.
 
# Function to perform query 1
def performQueryOne(num):
 
    # insert the element
    s.add(num)
 
# Function to perform query 2
def performQueryTwo(num):
 
    # erase the element
    s.remove(num)
 
# function to perform query 3
def performQueryThree():
 
    mini = min(s)
    maxi = max(s)
 
    return maxi - mini
 
# Driver Code
if __name__ == "__main__":
     
    s = set()
 
    # query type-1
    num = 3
    performQueryOne(num)
 
    # query type-1
    num = 5
    performQueryOne(num)
 
    # query type-1
    num = 6
    performQueryOne(num)
 
    # query type-2
    num = 5
    performQueryTwo(num)
 
    # query type-1
    num = 2
    performQueryOne(num)
 
    # query type-3
    print(performQueryThree())
 
# This code is contributed by Rituraj Jain

C#

// C# program to perform Queries
// to add, remove and return
// the difference of maximum and
// minimum using TreeSet.
using System;
using System.Collections.Generic;
 
class GFG
{
     
static SortedSet<int> t = new SortedSet<int>();
 
// function to perform query 1
static void performQueryOne(int num)
{
    // insert the element
    t.Add(num);
}
 
// function to perform query 2
static void performQueryTwo(int num)
{
    // erase the element
    t.Remove(num);
}
 
// function to perform query 3
static int performQueryThree()
{
    int mini = t.Min;
    int maxi = t.Max;
 
    return maxi - mini;
}
 
// Driver Code
public static void Main(String[] args)
{
    // query type-1
    int num = 3;
    performQueryOne(num);
 
    // query type-1
    num = 5;
    performQueryOne(num);
 
    // query type-1
    num = 6;
    performQueryOne(num);
 
    // query type-2
    num = 5;
    performQueryTwo(num);
 
    // query type-1
    num = 2;
    performQueryOne(num);
 
    // query type-3
    Console.WriteLine(performQueryThree());
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to perform Queries to
// add, remove and return
// the difference of maximum and minimum.
var s = new Set();
 
// function to perform query 1
function performQueryOne( num)
{
    // insert the element
    s.add(num);
}
 
// function to perform query 2
function performQueryTwo( num)
{
    // erase the element
    s.delete(num);
}
 
// function to perform query 3
function performQueryThree()
{
    var tmp = [...s].sort((a,b)=>a-b);
    var mini = tmp[0];
    var maxi = tmp[tmp.length-1];
 
    return maxi - mini;
}
 
// Driver Code
// query type-1
var num = 3;
performQueryOne(num);
// query type-1
num = 5;
performQueryOne(num);
// query type-1
num = 6;
performQueryOne(num);
// query type-2
num = 5;
performQueryTwo(num);
// query type-1
num = 2;
performQueryOne(num);
// query type-3
document.write( performQueryThree());
 
 
</script>
Producción

4

Complejidad de tiempo: O (log N) para cada consulta, ya que estamos usando el conjunto de árboles e insertar, eliminar y obtener el elemento mínimo o máximo tomará tiempo logN. 
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para el conjunto de árboles.

Publicación traducida automáticamente

Artículo escrito por Striver 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 *