Diseñe una estructura de datos que pueda soportar las siguientes operaciones en O(1) Time Complexity .
- insert(x): Inserta x en la estructura de datos. Devuelve True si x no estaba presente y False si ya estaba presente.
- remove(x): Elimina x de la estructura de datos, si está presente.
- getRandom(): Devuelve aleatoriamente cualquier valor presente en el flujo. La probabilidad de que se devuelva cada elemento debe ser linealmente proporcional al número de elementos del mismo valor que contiene la secuencia.
Enfoque: en el artículo anterior , ya hemos discutido un enfoque para este tipo de estructura de datos. Sin embargo, la estructura de datos anterior funcionó bien solo para valores únicos. En este artículo, diseñaremos una estructura de datos que también pueda manejar elementos duplicados.
El enfoque utilizado en este artículo es muy similar al enfoque anterior, pero para manejar los elementos duplicados, se usa un mapa de conjuntos para almacenar los índices de los elementos presentes en la array dinámica . Entendamos cada método de forma independiente.
- insertar(int x):
- Inserte x al final de la array dinámica nums[].
- Inserte el índice de x (es decir) nums.size() – 1 a mp[x] . Este mapa de conjuntos almacena todos los índices del elemento x presentes en el arreglo dinámico nums[] .
- eliminar (int x):
- Compruebe si x está presente en la secuencia mediante mp.count(x). Si está ausente, devuelve False .
- Si x está presente, el primer elemento del conjunto mp[x] se elimina y su valor se almacena en una variable indexRemoved . Ahora, si este elemento (es decir) indexRemoved es lo mismo que nums.length() – 1 vaya directamente al paso 6 porque esto significa que el elemento ya está en el último índice y ese elemento se elimina en tiempo constante.
- De lo contrario, para eliminar este elemento en un tiempo constante, este elemento se intercambia con el último elemento en la array dinámica. Por lo tanto, elimine el valor nums.size() – 1 del conjunto mp[nums[nums.size() – 1]] .
- Inserte el índice de valor en el conjunto mp[nums[nums.size() – 1]].
- Intercambie los elementos en el índice nums.size() – 1 e indexRemoved of nums.
- Elimine el último elemento de nums (la eliminación del final de Dynamic Array es una operación de tiempo constante).
- Si el conjunto mp[val] se vacía, borre val de mp.
- Devolver verdadero
- getRandom():
- Obtenga un número aleatorio entre 0 y nums.size() – 1.
- Devuelve el valor presente en este índice de nums.
A continuación se muestra la implementación del enfoque anterior:
// C++ program to design a data structure
// that supports insert, delete,
// getRandom in O(1) with duplicates
#include <bits/stdc++.h>
using namespace std;
class Stream {
private:
// Stores all the numbers present
// currently in the stream
vector<int> nums;
// Unordered ensure O(1) operation
unordered_map<int, unordered_set<int> > mp;
public:
// Function to insert values
// in the stream
bool insert(int val)
{
// Inserting val to the end of array
nums.push_back(val);
// Index at which val was inserted
int index = nums.size() - 1;
// Inserting the index inside the
// set mp[val]
mp[val].insert(index);
// Return True if only one val
// is present in the stream
return mp[val].size() == 1;
}
// Function to remove the value
// from the stream
bool remove(int val)
{
// If the value is not present
// in the stream
if (!mp.count(val))
return 0;
// Get the value of the first element
// of the mp[val] and store it
// in a variable named index
int index = *(mp[val].begin());
// Last Index of nums
int lastIndex = nums.size() - 1;
// Erase the index from mp[val] set
mp[val].erase(index);
// If index == lastIndex, then the
// element was already deleted
// from the stream
if (index != lastIndex) {
// Delete the lastIndex from
// mp[nums[lastIndex]] set
mp[nums[lastIndex]].erase(lastIndex);
// Insert index into mp[nums[lastIndex]] set
mp[nums[lastIndex]].insert(index);
// Swap the values at index and lastIndex
swap(nums[index], nums[lastIndex]);
}
// Delete the last element from nums
// This operation is O(1) operation
nums.pop_back();
// If the size of mp[val] is 0,
// val is absent from the stream
// and hence it is removed
if (mp[val].size() == 0)
mp.erase(val);
return 1;
}
// Function to get a random number
// from the stream of data
int getRandom()
{
// Get any random index from 0 to
// nums.length() - 1
int randomIndex = rand() % nums.size();
// Return the value at that index
return nums[randomIndex];
}
};
// Driver code
int main()
{
Stream myStream;
cout << myStream.insert(5) << endl;
cout << myStream.insert(6) << endl;
cout << myStream.insert(5) << endl;
cout << myStream.remove(6) << endl;
cout << myStream.remove(6) << endl;
cout << myStream.getRandom() << endl;
return 0;
}
Producción:
1 1 0 1 0 5