arrays - array - sorting algorithms comparison

Pregunta de tarea de matriz

Question

Te dan una matriz con enteros entre 1 y 1,000,000. Un entero está en la matriz dos veces. ¿Cómo puedes determinar cuál? ¿Puedes pensar en una forma de hacerlo usando poca memoria extra?

Algo:

• Solución 1:
  1. Tener una tabla hash
  2. Itera a través de una matriz y almacena sus elementos en la tabla hash
  3. Tan pronto como encuentre un elemento que ya está en la tabla hash, será el elemento dup
  Pros:
  • Funciona en O (n) tiempo y con solo 1 pase
  Contras:
  • Utiliza O (n) memoria adicional
• Solution2:
  1. Ordene la matriz usando la clase de fusión (tiempo O (nlogn))
  2. Analice nuevamente y si ve un elemento dos veces, obtiene el dup.
  Pros:
  • no usa memoria extra
  Contras:
  • El tiempo de ejecución es mayor que O (n)

¿Pueden pensar en alguna solución mejor?

Answer 1

¿Y qué hay del problema de encontrar TODOS los duplicados? ¿Se puede hacer esto en menos de O (n ln n) tiempo? (Ordenar y escanear) (Si desea restaurar la matriz original, lleve consigo el índice original y reordene después del final, lo que se puede hacer en el tiempo O (n))

Answer 2

Clasifique enteros ordenándolos en el lugar donde deberían estar. Si consigues "colisión", entonces encuentras el número correcto.

Complejidad del espacio O (1) (solo el mismo espacio que puede sobrescribirse) complejidad del tiempo menor que O (n) porque encontrará colisión estadísticamente antes de llegar al final.

Answer 3

Como una variante de su solución (2), puede usar radix sort . Sin memoria extra, y se ejecutará en tiempo lineal. Puedes argumentar que el tiempo también se ve afectado por el tamaño de la representación de los números, pero ya has dado límites para eso: el orden de radix se ejecuta en el tiempo O (kn), donde k es el número de dígitos que puedes ordenar por cada pase. Eso hace que todo el algoritmo O (7n) para la clasificación más O (n) para verificar el número duplicado - que es O (8n) = O (n).

Pros:

• Sin memoria extra
• En)

Contras:

• Necesita ocho O (n) pases.

Answer 4

En lugar de ordenar la matriz y luego verificar, sugeriría escribir una implementación de una función de clasificación de comparación que salga tan pronto como se encuentre el dup, lo que no requerirá memoria adicional (según el algoritmo que elija, obviamente) y un peor caso O (nlogn) hora (de nuevo, dependiendo del algoritmo), en lugar de una mejor (y promedio, dependiendo ...) de la hora O (nlogn).

Por ejemplo, una implementación de ordenación de fusión in situ.

http://en.wikipedia.org/wiki/Merge_sort

Answer 5

Este código python es una modificación de QuickSort :

def findDuplicate(arr):
orig_len = len(arr)
if orig_len <= 1:
return None
pivot = arr.pop(0)
greater = [i for i in arr if i > pivot]
lesser = [i for i in arr if i < pivot]
if len(greater) + len(lesser) != orig_len - 1:
return pivot
else:
return findDuplicate(lesser) or findDuplicate(greater)

Encuentra un duplicado en O (n logn)), creo. Utiliza memoria extra en la pila, pero puede reescribirse para usar solo una copia de los datos originales, creo:

def findDuplicate(arr):
orig_len = len(arr)
if orig_len <= 1:
return None
pivot = arr.pop(0)
greater = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] > pivot]
lesser = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] < pivot]
if len(arr):
return pivot
else:
return findDuplicate(lesser) or findDuplicate(greater)

Las listas de comprensiones que producen mayor y menor destruyen el original con llamadas a pop (). Si arr no está vacío después de eliminar mayor y menor de él, entonces debe haber un duplicado y debe ser pivote .

El código sufre los problemas habituales de desbordamiento de pila en los datos clasificados, por lo que es necesario un pivote aleatorio o una solución iterativa que ponga en cola los datos:

def findDuplicate(full):
import copy
q = [full]
while len(q):
arr = copy.copy(q.pop(0))
orig_len = len(arr)
if orig_len > 1:
pivot = arr.pop(0)
greater = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] > pivot]
lesser = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] < pivot]
if len(arr):
return pivot
else:
q.append(greater)
q.append(lesser)
return None

Sin embargo, ahora el código necesita tomar una copia profunda de los datos en la parte superior del ciclo, cambiando los requisitos de memoria.

Hasta aquí para la informática. El ingenuo algoritmo corta mi código en python, probablemente debido al algoritmo de clasificación de Python:

def findDuplicate(arr):
arr = sorted(arr)
prev = arr.pop(0)
for element in arr:
if element == prev:
return prev
else:
prev = element
return None

Answer 6

La pregunta es un poco ambigua; cuando la solicitud es "¿cuál?", ¿significa devolver el valor que está duplicado o la posición en la secuencia del duplicado? Si el primero, cualquiera de las siguientes tres soluciones funcionará; si es el último, el primero es el único que ayudará.

Solución n. ° 1: supone que la matriz es inmutable

Construye un mapa de bits; establece el n- ésimo bit mientras iteras a través de la matriz. Si el bit ya está configurado, ha encontrado un duplicado. Se ejecuta en tiempo lineal, y funcionará para cualquier matriz de tamaño.

El mapa de bits se creará con tantos bits como valores posibles en la matriz. A medida que iteras a través de la matriz, verificas el n- ésimo bit en la matriz. Si está configurado, has encontrado tu duplicado. Si no es así, configúrelo. (La lógica para hacer esto se puede ver en el pseudo-código en esta entrada de Wikipedia en matrices de bits o usar la clase System.Collections.BitArray ).

Solución n. ° 2: se supone que la matriz es mutable

Ordene la matriz y luego realice una búsqueda lineal hasta que el valor actual sea igual al valor anterior. Utiliza el menor recuerdo de todos. Puntos de bonificación por alterar el algoritmo de clasificación para detectar el duplicado durante una operación de comparación y terminar temprano.

Solución n. ° 3: (supone una longitud de matriz = 1.000,001)

1. Suma todos los enteros en la matriz.
2. De eso, reste la suma de los enteros 1 a 1,000,000 inclusive.
3. Lo que queda será tu valor duplicado.

Esto casi no requiere memoria extra, se puede hacer en una sola pasada si calcula las sumas al mismo tiempo.

La desventaja es que debe hacer todo el ciclo para encontrar la respuesta.

Las ventajas son la simplicidad y una alta probabilidad de que, de hecho, se ejecute más rápido que las otras soluciones.

Answer 7

Sugerencia: utilice la propiedad que A XOR A == 0 y 0 XOR A == A.

Answer 8

Suponiendo que todos los números de 1 a 1,000,000 están en la matriz , la suma de todos los números de 1 a 1,000,000 es (1,000,000)*(1,000,000 + 1)/2 = 500,000 * 1,000,001 = 500,000,500,000 .

Así que solo suma todos los números en la matriz, reste 500,000,500,000, y te quedarás con el número que ocurrió dos veces.

O (n) tiempo y O (1) memoria.

Si la suposición no es cierta , podría intentar usar un Filtro Bloom : se pueden almacenar mucho más comparativamente que una tabla hash (ya que solo almacenan datos de presencia), pero corren el riesgo de falsos positivos. Sin embargo, este riesgo puede estar limitado por nuestra elección de la cantidad de memoria para gastar en el filtro de floración.

Luego podemos usar el filtro de bloom para detectar posibles duplicados en el tiempo O (n) y verificar cada candidato en el tiempo O (n).

Answer 9

def singleton(array):
return reduce(lambda x,y:x^y, array)