Obtener elemento aleatorio y eliminarlo

Question

Problema: Necesito obtener un elemento aleatorio para un contenedor y también eliminarlo de ese contenedor. El contenedor no necesita ser ordenado. No me importa la orden.

• vector puede conseguirme elemento aleatorio en O(1) pero eliminarla sólo en O(N) Lista
• elimina elemento en O(1) pero sólo se puede conseguir elemento aleatorio en O(N)

Así que se me ocurrió una idea de hacer un vector personalizado que le permita eliminar cualquier elemento por su índice con O(1)+ complejidad. La idea es intercambiar el último elemento y un elemento que desea eliminar y luego pop_back(). Si necesita eliminar el último elemtent, solo pop_back(). El orden del vector no será el mismo pero obtienes un método de eliminación rápida.

Como puedo entender deque tengo acceso más lento por índice y peor complejidad de eliminación que mi solución pero no estoy 100% seguro.

Tengo curiosidad de que haya estructuras de datos que tengan acceso aleatorio y eliminación de elementos en O(1) o O(logN) por índice o mb por valor?

Answer 1

Tiene la solución, y parece perfectamente bien. La forma idiomática para escribir en C++ no es crear otra clase (y favordon't inherit from std::vector), pero sólo para escribir una función:

template <typename T> 
void remove_at(std::vector<T>& v, typename std::vector<T>::size_type n) 
{ 
    std::swap(v[n], v.back()); 
    v.pop_back(); 
} 

Uso:

remove_at(v, 42); 

Esto ofrece la misma excepción garantía como std::swap<T>.

Ahora, si desea devolver el objeto y tiene acceso a un compilador de C++ 11, puede hacerlo de la siguiente manera. La parte difícil es proporcionar la garantía excepción básica en todos los casos:

template <typename T> 
T remove_at(std::vector<T>&v, typename std::vector<T>::size_type n) 
{ 
    T ans = std::move_if_noexcept(v[n]); 
    v[n] = std::move_if_noexcept(v.back()); 
    v.pop_back(); 
    return ans; 
} 

hecho, que no quieren que el vector se puede dejar en un estado no válido si se produce una excepción durante una operación de movimiento.

Answer 2

Con O (n) la complejidad

vec.erase (vec.begin() + randomIdx); randomIdx sería entre 0 y vec.size() - 1

Si desea complejidad O (1) puede utilizar el contenedor de lista por ejemplo o cambiar el elemento por el último y eliminarlo en su lugar. (Como lo mencionaron los otros)

Answer 3

Sí, hay una solución, un árbol binario bien equilibrado.

Uno cada nodo que necesitaría para almacenar la cantidad de nodos en cada lado. De aquí es O (log N) para encontrar el enésimo elemento.

La eliminación del enésimo elemento también es O (registro N) ya que debe recorrer una copia de seguridad en árbol para corregir todos los recuentos. Cualquier reequilibrio sería O (log N) también a lo sumo.

Un árbol se considera bien equilibrado si ningún nodo de hoja tiene 2 nodos más profundos que otro. Busque árboles AVL para obtener un algoritmo de balanceo.

Realmente sería bueno si la biblioteca estándar "abriera" el uso de los árboles utilizados para std :: set y std :: map como una interfaz pública para usar en árboles personalizados.