Dadas las consultas Q de tipo 1, 2, 3 y 4 como se describe a continuación.
- Tipo-1: Inserta un número en la lista.
- Tipo-2: elimine solo una ocurrencia de un número si existe.
- Tipo-3: Imprime el elemento menos frecuente, si existen varios elementos, imprime el mayor entre ellos.
- Tipo-4: Imprime el elemento más frecuente, si existen varios elementos, imprime el más pequeño entre ellos.
La tarea es escribir un programa para realizar todas las consultas anteriores.
Ejemplos:
Entrada:
Consulta 1: 1 6
Consulta 2: 1 6
Consulta 3: 1 7
Consulta 4: 3
Consulta 5: 1 7
Consulta 6: 2 7
Consulta 7: 1 7
Consulta 8: 3
Consulta 9: 4
Salida:
7
7
6
Al responder a la Consulta 4, la frecuencia de 6 es 2 y el de
7 es 1, por lo tanto, el elemento menos frecuente es 7.
En Query8, el elemento menos frecuente es 6 y 7, así que imprima el más grande.
En Query9, el elemento más frecuente es 6 y 7, así que imprima el más pequeño.
Un enfoque ingenuo es utilizar cualquier estructura de datos (array, vector, ..) y almacenar todos los elementos. Usando una tabla hash , se puede almacenar la frecuencia de cada elemento. Mientras procesa la consulta de tipo 2, elimine una aparición de ese elemento del DS en el que se ha almacenado el elemento. Las consultas de tipo 3 y tipo 4 se pueden responder atravesando la tabla hash. La complejidad temporal será O(N) por consulta, donde N es el número de elementos hasta entonces en el DS.
Un enfoque eficiente será usar un contenedor establecido para responder a cada consulta. Usando dos conjuntos, una tabla hash, el problema anterior se puede resolver en O (log n) por consulta. Dos conjuntos s1y s2 , uno almacena {num, frecuencia} , mientras que el otro almacena {frecuencia, número} . Se utiliza un mapa hash que almacena la frecuencia de cada número. Diseñe el conjunto s2 utilizando la sobrecarga de operadores de modo que se ordene en orden ascendente de los primeros elementos. Si el primer elemento parece ser el mismo de uno o más elementos, el conjunto se ordenará en orden descendente de los segundos elementos. La función de sobrecarga operativa definida por el usuario será por lo tanto:
bool operator<(pr a, pr b) {
if(a.first == b.first) return a.second > b.second;
return a.first < b.first;
}
Note: Operator overloading only works with user-defined
data-types. pr is a struct which has first and second as two integers.
A continuación se muestra el algoritmo para resolver consultas de cada tipo:
- Tipo 1: verifique usando una tabla hash si el elemento existe. Si no existe, marque el número en la tabla hash . Inserte {num, 1} en el conjunto s1 y {1, num} en el conjunto2 usando insert() . Si existe anteriormente, obtenga la frecuencia de la tabla hash y elimine {num, frecuencia} de set1 y {frequency, num} de set2 usando la función find() y erase() . Inserte {num, frecuencia+1} en set1 y {frequency+1, num} en set2. Además, aumente el conteo en la tabla hash.
- Tipo 2: siga el mismo proceso que el anterior en la consulta tipo 1. La única diferencia es disminuir el conteo en la tabla hash e insertar {num, frecuencia-1} en set1 y {frequency-1, num} en set2.
- Type3: Imprime el elemento inicial que se puede obtener usando la función begin(), ya que el conjunto ha sido diseñado de tal manera que begin() devuelve el elemento menos frecuente. Si hay más de uno, devuelve el más grande.
- Tipo 4: Imprime el último elemento del conjunto que se puede obtener usando la función rbegin() en el conjunto.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program for performing
// Queries of insert, delete one
// occurrence of a number and
// print the least and most frequent element
#include <bits/stdc++.h>
using namespace std;
// user-defined data-types
struct pr {
int first;
int second;
};
// user-defined function to
// design a set
bool operator<(pr a, pr b)
{
if (a.first == b.first)
return a.second > b.second;
return a.first < b.first;
}
// declare a user-defined set
set<pr> s1, s2;
// hash map
unordered_map<int, int> m;
// Function to process the query
// of type-1
void type1(int num)
{
// if the element is already there
if (m[num]) {
// get the frequency of the element
int cnt = m[num];
// returns an iterator pointing to
// position where the pair is
auto it1 = s1.find({ num, cnt });
auto it2 = s2.find({ cnt, num });
// deletes the pair from sets
s1.erase(it1);
s2.erase(it2);
// re-insert the pair by increasing
// frequency
s1.insert({ num, m[num] + 1 });
s2.insert({ m[num] + 1, num });
}
// if the element is not there in the list
else {
// insert the element with frequency 1
s1.insert({ num, 1 });
s2.insert({ 1, num });
}
// increase the count in hash-table
m[num] += 1;
}
// Function to process the query
// of type-2
void type2(int num)
{
// if the element exists
if (m[num]) {
// get the frequency of the element
int cnt = m[num];
// returns an iterator pointing to
// position where the pair is
auto it1 = s1.find({ num, cnt });
auto it2 = s2.find({ cnt, num });
// deletes the pair from sets
s1.erase(it1);
s2.erase(it2);
// re-insert the pair by increasing
// frequency
s1.insert({ num, m[num] - 1 });
s2.insert({ m[num] - 1, num });
// decrease the count
m[num] -= 1;
}
}
// Function to process the query
// of type-3
int type3()
{
// if the set is not empty
// return the first element
if (!s1.empty()) {
auto it = s2.begin();
return it->second;
}
else
return -1;
}
// Function to process the query
// of type-4
int type4()
{
// if the set is not empty
// return the last element
if (!s1.empty()) {
auto it = s2.rbegin();
return it->second;
}
else
return -1;
}
// Driver Code
int main()
{
// Queries
// inserts 6, 6 and 7
type1(6);
type1(6);
type1(7);
// print the answer to query of type3
cout << type3() << endl;
// inserts 7
type1(7);
// deletes one occurrence of 7
type2(7);
// inserts 7
type1(7);
// print the answer to query of type3
cout << type3() << endl;
// print the answer to query of type4
cout << type4() << endl;
return 0;
}
7 7 6
Complejidad de tiempo: O (log N) por consulta.
Espacio Auxiliar: O(N)