Duplicar posible:
Determining if an unordered vector<T> has all unique elementsControl de duplicidad en un vector
tengo que comprobar un vector de duplicados. Cuál es la mejor manera de abordar esto:
Tomo el primer elemento, compáralo con todos los demás elementos en el vector. Luego toma el siguiente elemento y haz lo mismo, y así sucesivamente.
¿Es esta la mejor manera de hacerlo, o hay una forma más eficiente de verificar dúplex?
Utilice un hash table en el que inserte cada elemento. Antes de insertar un elemento, verifique si ya está allí. Si es así, tienes un duplicado. Esto es O(n)en promedio, pero el peor caso es tan malo como su método actual.
O bien, puede usar un set para hacer lo mismo en el peor caso de O(n log n). Esto es tan bueno como la solución de clasificación, excepto que no cambia el orden de los elementos (aunque usa más memoria desde que creaste un conjunto).
Otra forma es copiar su vector a otro vector, ordenarlo y verificar los elementos adyacentes allí. No estoy seguro de si esto es más rápido que la solución establecida, pero creo que ordenar agrega menos sobrecarga que los árboles de búsqueda equilibrada que usa un conjunto, por lo que debería ser más rápido en la práctica.
Por supuesto, si no te importa mantener el orden original de los elementos, simplemente ordena el vector inicial.
No es tan "tan bueno" como la solución de clasificación. Es el mismo orden de tiempo de ejecución de gran O, pero el factor constante en la clasificación de un vector, que garantiza tener sus elementos contiguos en la memoria, será significativamente menor que el algoritmo que usa el conjunto. No me sorprendería si fuera el doble de rápido. +1 de todos modos. Creo que tienes la mejor respuesta. –
@A. Levy: cierto, mencioné otro método. – IVlad
Una ordenación de Radix puede ser incluso más rápida que O (n log n). http://en.wikipedia.org/wiki/Radix_sort –
Ordenar y luego comparar elementos adyacentes es el camino a seguir. Un ordenamiento toma comparaciones O (n log n), y luego un n-1 adicional para comparar elementos adyacentes.
El esquema en la pregunta tomaría (n^2)/2 comparaciones.
Si el vector es un contenedor STL, la solución es fácil:
Por ejemplo:
std::sort (myvec.begin(), myvec.end());
std::unique (myvec.begin(), myvec.end());
en cuenta que una std :: unique en realidad no eliminará los duplicados, sino que los moverá al final del contenedor y devolverá un itera tor al primer duplicado. Por lo tanto, dependiendo de la situación, es posible que desee usar std :: remove para eliminar la cola del contenedor, o use std :: copy para copiar solo los no duplicados a otro contenedor.
Para aclarar, los duplicados no se mueven al final del rango; solo se eliminan del frente del rango. Los valores de los elementos después del nuevo final devuelto por 'std :: unique()' no están especificados. Si solo quiere probar si el rango no contiene duplicados, 'std :: adjacent_find()' es más eficiente que usar 'std :: unique()'. –
Tienes razón. Std :: unique coloca primero todos los elementos únicos y no especifica qué sucede con el resto del contenedor. Sin embargo, lo más importante es recordar que debe usar el iterador devuelto y no asumir que su contenedor solo contiene elementos únicos. Tienes que limpiar manualmente la cola del contenedor. – Patrick
También puede usar binary_search.
Éstos son dos buenos ejemplos que le ayudará a:
Si no se preocupan por un ocasional falso positivo, se puede utilizar un Bloom Filter para detectar duplicados probables la colección. Si no se pueden aceptar falsos positivos, tome los valores que fallan el filtro y ejecute un segundo pase de detección sobre ellos. La lista de valores fallidos debe ser bastante pequeña, aunque será necesario compararla con la entrada completa.
duplicado de [Determinación de si un vector no ordenada tiene todos los elementos únicos] (http://stackoverflow.com/questions/2769174/determining-if-an-unordered-vectort-has-all-unique-elements) –
Can usted modifica el vector? Si no, ¿tiene memoria para asignar una copia? – florin