Pregunta ¿Es posible eliminar duplicados de una lista ordenada en menos de O (n) tiempo?


Sospecho que hay una forma de ahorrar si localizas el otro extremo de un rango de valores repetidos más rápido que al iterar a través de esa sublista


8
2017-11-10 21:50


origen


Respuestas:


En general, no. Imagine una lista de N duplicados. Tendría que hacer eliminaciones de N-1, por lo tanto, O (N).

Si especifica una estructura de datos particular con mejor que O (1) eliminación de elementos, entonces podría haber una mejor manera para ciertos tipos de entradas.

Incluso si puede eliminar eficientemente un rango de elementos en O (1), y tarda O (1) en encontrar un duplicado - imagine una lista donde hay N / 2 pares de duplicados. Aún tendrá que hacer N / 2 búsquedas y eliminar N / 2 rangos, ambos de los cuales son O (N).

(También hay un poco de ambigüedad ya que el título de la pregunta es 'eliminar duplicados', pero el cuerpo es específico para eliminar un rango)

Si la lista resultante de su ordenamiento tiene la siguiente representación: cada nodo tiene un valor y un recuento de ocurrencia para eso, luego eliminar las duplicaciones para un valor establecerá trivialmente el recuento en 1 para ese nodo. ( UN lista de saltos probablemente tenga características similares, asumiendo un entorno decente recogido de basura donde no hay costo para reclamar memoria), por lo que sería O (1) para una duplicación. Si necesitas eliminar todas duplicados de la lista, todavía sería O (N).


12
2017-11-10 21:57



En general, no es así, porque siempre puedes construir un caso en el que tengas O (n) (una lista sin duplicados). Sin embargo, si comienza a hacer suposiciones sobre los datos (por ejemplo, que hay como mucho log n elementos distintos), puede obtener algo mejor (aunque no estoy seguro en este caso particular).

Por supuesto, esto supone que tienes alguna forma de hacer "eliminaciones masivas" eficientes, lo que significa que puedes eliminar cualquier rango de elementos iguales en O (1), independientemente de su tamaño.


3
2017-11-10 22:04



No puede haber

en cuanto a comparar todos los elementos con el otro, necesitamos hacer n * (n-1) = n2-n comparaciones ... `


1
2017-11-11 11:15



Me gustaría un enfoque de "búsqueda binaria" para encontrar los extremos de los rangos:

Supongamos que tenemos una lista ordenada de n elementos.

  1. Compare los elementos 1-st y n-th - si es igual a toda la lista es un duplicado.
  2. Seleccione un elemento intermedio (n / 2)
  3. Ejecute la búsqueda recursivamente para dos sublistas.

-2
2017-11-10 21:57