Diseñe una estructura de datos que admita las siguientes operaciones en tiempo Θ(1).
- insert(x): inserta un elemento x en la estructura de datos si aún no está presente.
- remove(x): elimina el elemento x de la estructura de datos si está presente.
- search(x): busca un elemento x en la estructura de datos.
- getRandom(): Devuelve un elemento aleatorio del conjunto de elementos actual
Podemos usar hashing para admitir las primeras 3 operaciones en tiempo Θ(1). ¿Cómo hacer la 4ª operación? La idea es usar una array redimensionable (ArrayList en Java, vector en C) junto con hashing. Las arrays redimensionables admiten inserción en Θ(1) complejidad de tiempo amortizado . Para implementar getRandom(), simplemente podemos elegir un número aleatorio de 0 a tamaño 1 (el tamaño es el número de elementos actuales) y devolver el elemento en ese índice. El mapa hash almacena valores de array como claves e índices de array como valores.
A continuación se detallan las operaciones.
- insertar(x)
- Compruebe si x ya está presente haciendo una búsqueda de mapa hash.
- Si no está presente, insértelo al final de la array.
- Agregue también en la tabla hash, x se agrega como clave y el último índice de array como índice.
- eliminar (x)
- Compruebe si x está presente haciendo una búsqueda de mapa hash.
- Si está presente, busque su índice y elimínelo de un mapa hash.
- Intercambie el último elemento con este elemento en una array y elimine el último elemento.
El intercambio se realiza porque el último elemento se puede eliminar en tiempo O(1). - Actualice el índice del último elemento en un mapa hash.
- obtener al azar()
- Genera un número aleatorio desde 0 hasta el último índice.
- Devuelve el elemento de la array en el índice generado aleatoriamente.
- buscar(x)
- Realice una búsqueda de x en el mapa hash.
A continuación se muestra la implementación de la estructura de datos.
C++
/* C++ program to design a DS that supports following operations
in Theta(n) time
a) Insert
b) Delete
c) Search
d) getRandom */
#include<bits/stdc++.h>
using namespace std;
// class to represent the required data structure
class myStructure
{
// A resizable array
vector <int> arr;
// A hash where keys are array elements and values are
// indexes in arr[]
map <int, int> Map;
public:
// A Theta(1) function to add an element to MyDS
// data structure
void add(int x)
{
// If element is already present, then nothing to do
if(Map.find(x) != Map.end())
return;
// Else put element at the end of arr[]
int index = arr.size();
arr.push_back(x);
// and hashmap also
Map.insert(std::pair<int,int>(x, index));
}
// function to remove a number to DS in O(1)
void remove(int x)
{
// element not found then return
if(Map.find(x) == Map.end())
return;
// remove element from map
int index = Map.at(x);
Map.erase(x);
// swap with last element in arr
// then remove element at back
int last = arr.size() - 1;
swap(arr[index], arr[last]);
arr.pop_back();
// Update hash table for new index of last element
Map.at(arr[index]) = index;
}
// Returns index of element if element is present, otherwise null
int search(int x)
{
if(Map.find(x) != Map.end())
return Map.at(x);
return -1;
}
// Returns a random element from myStructure
int getRandom()
{
// Find a random index from 0 to size - 1
srand (time(NULL));
int random_index = rand() % arr.size();
// Return element at randomly picked index
return arr.at(random_index);
}
};
// Driver main
int main()
{
myStructure ds;
ds.add(10);
ds.add(20);
ds.add(30);
ds.add(40);
cout << ds.search(30) << endl;
ds.remove(20);
ds.add(50);
cout << ds.search(50) << endl;
cout << ds.getRandom() << endl;
}
// This code is contributed by Aditi Sharma
Java
/* Java program to design a data structure that support following operations
in Theta(n) time
a) Insert
b) Delete
c) Search
d) getRandom */
import java.util.*;
// class to represent the required data structure
class MyDS
{
ArrayList<Integer> arr; // A resizable array
// A hash where keys are array elements and values are
// indexes in arr[]
HashMap<Integer, Integer> hash;
// Constructor (creates arr[] and hash)
public MyDS()
{
arr = new ArrayList<Integer>();
hash = new HashMap<Integer, Integer>();
}
// A Theta(1) function to add an element to MyDS
// data structure
void add(int x)
{
// If element is already present, then nothing to do
if (hash.get(x) != null)
return;
// Else put element at the end of arr[]
int s = arr.size();
arr.add(x);
// And put in hash also
hash.put(x, s);
}
// A Theta(1) function to remove an element from MyDS
// data structure
void remove(int x)
{
// Check if element is present
Integer index = hash.get(x);
if (index == null)
return;
// If present, then remove element from hash
hash.remove(x);
// Swap element with last element so that remove from
// arr[] can be done in O(1) time
int size = arr.size();
Integer last = arr.get(size-1);
Collections.swap(arr, index, size-1);
// Remove last element (This is O(1))
arr.remove(size-1);
// Update hash table for new index of last element
hash.put(last, index);
}
// Returns a random element from MyDS
int getRandom()
{
// Find a random index from 0 to size - 1
Random rand = new Random(); // Choose a different seed
int index = rand.nextInt(arr.size());
// Return element at randomly picked index
return arr.get(index);
}
// Returns index of element if element is present, otherwise null
Integer search(int x)
{
return hash.get(x);
}
}
// Driver class
class Main
{
public static void main (String[] args)
{
MyDS ds = new MyDS();
ds.add(10);
ds.add(20);
ds.add(30);
ds.add(40);
System.out.println(ds.search(30));
ds.remove(20);
ds.add(50);
System.out.println(ds.search(50));
System.out.println(ds.getRandom());
}
}
Python3
'''
Python program to design a DS that
supports following operations
in Theta(n) time:
a) Insert
b) Delete
c) Search
d) getRandom
'''
import random
# Class to represent the required
# data structure
class MyDS:
# Constructor (creates a list and a hash)
def __init__(self):
# A resizable array
self.arr = []
# A hash where keys are lists elements
# and values are indexes of the list
self.hashd = {}
# A Theta(1) function to add an element
# to MyDS data structure
def add(self, x):
# If element is already present,
# then nothing has to be done
if x in self.hashd:
return
# Else put element at
# the end of the list
s = len(self.arr)
self.arr.append(x)
# Also put it into hash
self.hashd[x] = s
# A Theta(1) function to remove an element
# from MyDS data structure
def remove(self, x):
# Check if element is present
index = self.hashd.get(x, None)
if index == None:
return
# If present, then remove
# element from hash
del self.hashd[x]
# Swap element with last element
# so that removal from the list
# can be done in O(1) time
size = len(self.arr)
last = self.arr[size - 1]
self.arr[index], \
self.arr[size - 1] = self.arr[size - 1], \
self.arr[index]
# Remove last element (This is O(1))
del self.arr[-1]
# Update hash table for
# new index of last element
self.hashd[last] = index
# Returns a random element from MyDS
def getRandom(self):
# Find a random index from 0 to size - 1
index = random.randrange(0, len(self.arr))
# Return element at randomly picked index
return self.arr[index]
# Returns index of element
# if element is present,
# otherwise none
def search(self, x):
return self.hashd.get(x, None)
# Driver Code
if __name__=="__main__":
ds = MyDS()
ds.add(10)
ds.add(20)
ds.add(30)
ds.add(40)
print(ds.search(30))
ds.remove(20)
ds.add(50)
print(ds.search(50))
print(ds.getRandom())
# This code is contributed
# by Saurabh Singh
Producción
2 3 30
Este artículo es una contribución de Manish Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA