arrays - array - sorting algorithms comparison

Encuentra un número donde aparezca exactamente N/2 veces (20)

Aquí está una de mis preguntas de la entrevista. Dado un conjunto de N elementos y donde un elemento aparece exactamente N / 2 veces y el resto de elementos N / 2 son únicos . ¿Cómo encontrarías el elemento con un mejor tiempo de ejecución?

Recuerde que los elementos no están ordenados y puede asumir que N es par. Por ejemplo,

input array [] = { 10, 2, 3, 10, 1, 4, 10, 5, 10, 10 }

Entonces aquí 10 aparece exactamente 5 veces, lo cual es N / 2.

Conozco una solución con O (n) tiempo de ejecución. Pero aún estoy deseando saber una mejor solución con O (log n).

Algorithm RepeatedElement(a, n)

while (true) do { i=Random() mod n+1; j=Random() mod n+1; // i and j are random numbers in the range [1,n] if ((i ≠ j) and a[i]=a[j])) then return; }

Aquí está la respuesta de Don Johe en Ruby:

#!/usr/bin/ruby1.8 def find_repeated_number(a) return nil unless a.size >= 3 (0..a.size - 3).each do |i| [ [0, 1], [0, 2], [1, 2], ].each do |j1, j2| return a[i + j1] if a[i + j1] == a[i + j2] end end end p find_repeated_number([1, 1, 2]) # => 1 p find_repeated_number([2, 3, 2]) # => 1 p find_repeated_number([4, 3, 3]) # => 1

En)

Aquí está mi intento de probar por qué esto no se puede hacer en menos de O (n) accesos a la matriz (en el peor de los casos, que seguramente es el único caso interesante en este ejemplo):

Supongamos que existe un algoritmo de registro (n) en el peor de los casos. Este algoritmo accede a la matriz en la mayoría de las veces log (n). Dado que no puede hacer suposiciones sobre qué elementos están en dónde, permítame elegir qué elementos log (n) ve. Elegiré darle los primeros elementos únicos de log (n). Todavía no ha encontrado el duplicado, y todavía existen n / 2 - log (n) elementos únicos para que los alimente si es necesario. De hecho, no puedo ser forzado a darle un número duplicado hasta que haya leído n / 2 elementos. Por lo tanto, tal algoritmo no puede existir.

Desde un punto de vista puramente intuitivo, esto parece imposible. El registro (4 mil millones) es 32. Entonces, con un conjunto de 4 mil millones de números, 2 mil millones de los cuales son únicos, sin ningún orden en particular, ¿hay una manera de encontrar el elemento duplicado al verificar solo 32 elementos?

Contrariamente a las respuestas anteriores, existe una solución con el peor comportamiento posible, O (log n) RUN TIME . El problema no es encontrar una solución con O (log N) comparaciones en el peor de los casos (lo cual es imposible), sino hacerlo O (log N) tiempo.

Si puedes hacer N comparaciones en paralelo, la solución es una división y conquista trivial. No es muy práctico en el mundo real, pero es una pregunta de entrevista, no un problema del mundo real.

Actualización: creo que puede hacerlo en tiempo constante con procesadores O (N)

Creo que simplemente necesitas analizar a través de la matriz manteniendo una acumulación de dos elementos. Como N / 2 es igual y el resto está garantizado para ser distinto, debe haber un lugar i en su matriz donde

a[i] == a[i-1] OR a[i] == a[i-2]

iterar una vez a través de su matriz y tiene una complejidad de aproximadamente 2 * N que debería estar bien dentro de O (N).

Esta respuesta es algo similar a la respuesta de Ganesh M y Dougie, pero creo que es un poco más simple.

En primer lugar, ya pasó la hora de acostarme y debería saber que no debo publicar el código en público sin haberlo probado antes, yada, yada. Espero que las críticas que recibo sean al menos educativas. :-)

Creo que el problema se puede replantear como: "Encuentra el número que aparece más de una vez".

En el peor de los casos, tendríamos que recorrer un poco más de la mitad de la lista (1 + N / 2) antes de encontrar la segunda instancia de un número no exclusivo.

Ejemplo de peor caso: array [] = {1, 2, 3, 4, 5, 10, 10, 10, 10, 10}

Sin embargo, en promedio , solo tendríamos que iterar 3 o 4 elementos, ya que la mitad de los elementos contendrá el número no exclusivo, es decir, aproximadamente todos los demás números.

Ejemplos de distribución perfectamente uniformes:

array [] = {1, 10, 2, 10, 3, 10, 4, 10, 5, 10}
array [] = {10, 1, 10, 2, 10, 3, 10, 4, 10, 5}

En otras palabras, incluso si N = 1 millón solo necesitarías buscar; en promedio, los primeros 3 o 4 elementos antes de descubrir un duplicado.

¿Cuál es la notación O grande para un tiempo de ejecución fijo / constante que no aumenta con N?

Código:

int foundAt = -1; for (int i=0; (i<N) && (foundAt==-1); i++) { for (int j=i+1; j<N; j++) { if (array[i] == array[j]) { foundAt = i; break; } } } int uniqueNumber = array[foundAt];

Es bastante simple ver que no existe ningún algoritmo O (log n). Claramente, debe mirar los elementos de la matriz para determinar cuál es el elemento repetido, pero no importa el orden en el que elija mirar los elementos, los elementos del primer piso (n / 2) que vea podrían ser todos únicos. Simplemente podrías tener mala suerte. Si eso sucediera, no tendrías forma de saber cuál era el elemento repetido. Dado que no funcionará ningún algoritmo que use menos de un piso (n / 2) referencias de matriz o menos en cada ejecución, definitivamente no hay algoritmo sublineal.

Esta es una pregunta de entrevista pobre.

Usted no sabe la respuesta a ti mismo.
No tiene ningún caso comercial detrás, por lo que tendrá dificultades para explicárselo al candidato.

Sobre todo por el primero. ¿Qué estás buscando? ¿Que el candidato debe proponer esta solución O (log n) que no sabe que existe? Si tiene que preguntarle a , ¿es esto algo que puede esperar razonablemente que un candidato presente en una entrevista?

Hay una solución de tiempo constante si está listo para aceptar una pequeña probabilidad de error. Muestra aleatoriamente dos valores de la matriz, si son los mismos, encontró el valor que estaba buscando. En cada paso, tienes una probabilidad de 0,75 de no terminar. Y debido a que para cada épsilon, existe una n tal que (3/4) ^ n <eps, podemos muestrear como máximo n y devolver un error si no encontramos un par coincidente.

También tenga en cuenta que, si seguimos muestreando hasta que encontramos un par, el tiempo de ejecución esperado es constante, pero el tiempo de ejecución en el peor de los casos no está limitado.

La respuesta es sencilla ... y puede lograrse en el peor de los casos (n / 2 + 1) comparaciones

Compare los primeros números por pares (n-2), es decir, compare nos. en 0 y 1, luego en 2 y 3 y así sucesivamente ... total de comparaciones n / 2 -1. Si encontramos números idénticos en cualquiera de las comparaciones anteriores ... tenemos el número repetido ... más:
Tome cualquiera de los últimos dos números restantes (digamos el segundo último que tomé) y compárelo con los números del segundo último par ... si ocurre una coincidencia ... segundo último no. es la repetida, de lo contrario la última es la repetida ... en las 2 comparaciones.

Comparaciones totales = n / 2 - 1 + 2 = n / 2 + 1 (el peor de los casos) No creo que exista ningún método O (log n) para lograr esto

Mi respuesta fue:

Divida N elementos en [N / 3] partes (es decir) cada parte tendrá 3 elementos.
Ahora compara estos 3 elementos entre sí. - 3 comparaciones
Al menos una de las partes tendrá dos copias del mismo elemento. De ahí el número.

Tiempo de ejecución - O (N)

No puedes hacer esto en tiempo sublineal porque necesitas leer la matriz. Para procesar una matriz de un millón de registros en tiempo logarítmico se requeriría solo la lectura de 20 elementos (log2), claramente imposible. Después de todo, si asume que el primer duplicado encontrado se repite N / 2 veces, sigue siendo O (n) porque es posible que deba buscar 500,001 elementos para encontrar un duplicado.

Puede hacer esto en O (n) si asume que los enteros no son negativos. Funciona así (pseudo-Java):

int repeatedNumber = -1; // sentinel value int count = 0; BitSet bits = new BigSet(); // this bitset needs to have 2^31 bits, roughly 2.1 billion boolean duplicate = false; for (int i : elements) { if (bits[i].isSet()) { if (repeatedNumber == -1) { repeatedNumber = i; count = 1; } else if (i == repeatedNumber) { count++; } else { System.out.println("Array has more than one repeated element"); duplicate = true; break; } } else { bits[i].set(); } } if (!duplicate && repeatedNumber != -1 && count == elements.length/2) { System.out.println(repeatedNumber + " occurred " + count + " times. The rest of the elements are unique"); } else { System.out.println("Not true"); }

Se utiliza un método similar para ordenar una matriz de enteros únicos en O (n) (clasificación por radix).

Para el comportamiento determinista en el peor de los casos, O (N) es correcto (ya he visto más de una prueba en las respuestas anteriores).

Sin embargo, la teoría algorítmica moderna no se ocupa solo del comportamiento del caso más desfavorable (es por eso que hay tantos otros grandes y pequeños además de la gran O, aunque los programadores perezosos a menudo usan la gran O incluso cuando tienen en mente lo que tienen en mente está más cerca del big-theta O del big-omega ;-), ni solo con el determinismo (con la prueba de primalidad de Miller-Rabin ...;).

Cualquier muestra aleatoria de K <N elementos no mostrará duplicados con una probabilidad de que <2 ** K - se reduzca fácil y rápidamente a esencialmente tan bajo como lo desee, sin importar qué sea N (por ejemplo, podría reducirlo a menos de la probabilidad que un rayo cósmico aleatorio se volcará accidental e indetectable un poco en tu memoria ;-) - esta observación apenas requiere la creatividad que Rabin y Miller necesitaron para encontrar su método probabilístico de prueba principal ;-).

Esto haría una pregunta de entrevista bastante mala. Con frecuencia, los candidatos que no tienen éxito plantean a menudo preguntas menos malas. Por ejemplo, una pregunta típica podría ser, dada una matriz de N elementos, sin saber si hay un elemento mayoritario, para determinar si hay uno, y cuál es, en tiempo O (N) y O (1) auxiliar espacio (por lo que no puede configurar una tabla hash o algo para contar las ocurrencias de diferentes valores). El "Enfoque de votación de Moore" es una buena solución (probablemente la mejor) para esa valiosa pregunta de entrevista.

Otra variación interesante: ¿qué pasa si tiene 10**18 números de 64 bits (el valor de los datos de 8 Terabytes en general, por ejemplo, en un bigtable o clon del mismo), y tantas máquinas como desee, cada una con aproximadamente 4GB de RAM en una LAN bastante rápida, digamos una que es sustancialmente mejor que GB Ethernet. ¿Cómo puede usted evitar el problema en esas condiciones? ¿Qué pasa si tienes que usar mapreduce / hadoop? ¿Qué sucede si tiene la libertad de diseñar su propio marco dedicado solo para este problema? ¿Podría obtener un mejor rendimiento que con mapreduce? ¿Cuánto mejor, en la granularidad de la estimación de fondo de envolvente? No conozco ningún algoritmo publicado para ESTA variante, por lo que puede ser una gran prueba si desea verificar la facilidad general de un candidato con enfoques altamente distribuidos para el cálculo de tera-escala ...

Para hacerlo menos que O (n), no deberías leer todos los números.
Si sabe que hay un valor que satisface la relación, entonces podría probar un pequeño subconjunto y mostrar que solo un número aparece las veces suficientes para cumplir con la relación. Tendrías que asumir que los valores están distribuidos razonablemente uniformemente.

Editar. tendría que leer n / 2 para demostrar que existía tal número, pero si sabía que existía un número y solo quería encontrarlo, podría leer muestras de sqrt (n)

Peter tiene toda la razón. Aquí hay una manera más formal de reafirmar su prueba:

Sea el conjunto S un conjunto que contiene N elementos. Es la unión de dos conjuntos: p, que contiene un símbolo α repetido N / 2 veces, y q, que contiene N / 2 símbolos únicos ω ₁ ..ω _{n / 2} . S = p ∪ q.

Supongamos que hay un algoritmo que puede detectar su número duplicado en las comparaciones de log (n) en el peor de los casos para todos los N> 2. En el peor de los casos, significa que no existe ningún subconjunto r such S tal que | r | = log ₂ N donde α ∉ r .

Sin embargo, debido a que S = p q, hay | p | muchos elementos ≠ α en S. | p | = N / 2, entonces ∀ N / 2 tal que N / 2 ≥ log ₂ N, debe existir al menos un conjunto r ⊂ S tal que | r | = log ₂ N y α ∉ r. Este es el caso para cualquier N ≥ 3. Esto contradice la suposición anterior, por lo que no puede haber tal algoritmo.

QED.

Replanteando mi solución de un comentario a la versión de Ganesh para que pueda formatearla:

for (i=0; i<N-2; i+=3) { if a[i] == a[1+1] || a[i] == a[i+2] return a[i]; if a[i+1] == a[i+2] return a[i+1]; } return a[N-1]; // for very small N

Probabilidad de ganar después de 1 iteración: 50%

Probabilidad de ganar después de 2 iteraciones: 75%

Etc.

En el peor de los casos, O (n) tiempo O (1) espacio.

Tenga en cuenta que después de las iteraciones N / 4 ha agotado todos los números únicos N / 2, por lo que este bucle nunca se repetirá a través de más de 3/4 de la matriz si es como se especifica.

Si estoy entendiendo el problema correctamente: todo lo que sabemos sobre la matriz es su longitud y tiene (N / 2) +1 elementos únicos, donde 1 elemento se repite N / 2 veces (en ningún orden específico).

Creo que esto tiene un límite estricto de O (N) para la solución, ya que realmente no puede afirmar (para una matriz genérica) que ha encontrado el número sin encontrar al menos 2 del mismo número. No creo que exista una búsqueda de una matriz desordenada que pueda detectar un duplicado en O (logN) (corríjame si me equivoco). Siempre deberá leer al menos N / 2 +1 elementos en el peor de los casos.

Si le dicen que el elemento que está buscando no es el único, la forma más rápida de hacerlo es iterar a lo largo de la matriz hasta que encuentre dos iguales y luego devuelva ese elemento y deje de buscar. A lo sumo tienes que buscar la mitad de la matriz.

Creo que esto es O (n), así que supongo que realmente no ayuda.

Parece demasiado simple, así que creo que no entiendo el problema correctamente.

Similar a https://.com/a/1191881/199556 explicación.

Comparemos 3 elementos (3 operaciones de comparación) en el peor de los casos, el elemento "igual" aparecerá una vez. Así que reducimos la cola en 3 y reducimos la cuenta de "mismos" elementos en uno.

En el paso final (después de k iteraciones) nuestra cola contendrá (n / 2) - k "mismos" elementos. Vamos a comparar la longitud de la cola.

Por un lado, será n-3k por otro lado (n / 2) - k + 1. Los últimos elementos no conocidos pueden existir.

n-3k = (n / 2) - k + 1

k = 1/4 * (n-2)

Después de k iteraciones seguramente obtendremos resultados.

Número de comparaciones 3/4 * (n-2)

Supongamos que tienes un algoritmo de Python como este:

import math import random def find_duplicate(arr, gap): cost, reps = 0, 0 while True: indexes = sorted((random.randint(0,len(arr)-i-1) for i in xrange(gap)), reverse=True) selection = [arr.pop(i) for i in indexes] selection_set = set(selection) cost += len(selection) reps += 1 if len(selection) > len(selection_set): return cost, reps

La idea es que arr es su conjunto de valores y la brecha es el log base-2 del tamaño. Cada vez que selecciona elementos de brecha y ve si hay valores duplicados. Si es así, devuelva su costo (en el recuento de elementos examinados) y el número de iteraciones (donde examina los elementos log2 (tamaño) por iteración). De lo contrario, mira otro conjunto de tamaño vacío .

El problema con la evaluación comparativa de este algoritmo es que la creación de los datos cada vez que se realiza el ciclo y la alteración de los datos es costosa, suponiendo una gran cantidad de datos. (Inicialmente, estaba haciendo 1 000 000 elementos con 10 000 000 iteraciones).

Así que vamos a reducir a un problema equivalente. Los datos se pasan como n / 2 elementos únicos y n / 2 elementos repetidos. El algoritmo selecciona los índices aleatorios de los elementos log2 (n) y comprueba si hay duplicados. Ahora ni siquiera tenemos que crear los datos y eliminar los elementos examinados: solo podemos verificar si tenemos dos o más índices en el punto medio . Seleccione los índices de huecos , verifique 2 o más en el punto medio: devuelva si se encuentra, de lo contrario repita.

import math import random def find_duplicate(total, half, gap): cost, reps = 0, 0 while True: indexes = [random.randint(0,total-i-1) for i in range(gap)] cost += gap reps += 1 above_half = [i for i in indexes if i >= half] if len(above_half) >= 2: return cost, reps else: total -= len(indexes) half -= (len(indexes) - len(above_half))

Ahora maneja el código así:

if __name__ == ''__main__'': import sys import collections import datetime for total in [2**i for i in range(5, 21)]: half = total // 2 gap = int(math.ceil(math.log10(total) / math.log10(2))) d = collections.defaultdict(int) total_cost, total_reps = 0, 1000*1000*10 s = datetime.datetime.now() for _ in xrange(total_reps): cost, reps = find_duplicate(total, half, gap) d[reps] += 1 total_cost += cost e = datetime.datetime.now() print "Elapsed: ", (e - s) print "%d elements" % total print "block size %d (log of # elements)" % gap for k in sorted(d.keys()): print k, d[k] average_cost = float(total_cost) / float(total_reps) average_logs = average_cost / gap print "Total cost: ", total_cost print "Average cost in accesses: %f" % average_cost print "Average cost in logs: %f" % average_logs print

Si prueba esta prueba, encontrará que la cantidad de veces que el algoritmo tiene que hacer múltiples selecciones disminuye con la cantidad de elementos en los datos. Es decir, su costo promedio en registros se aproxima asintóticamente 1 .

elements accesses log-accesses 32 6.362279 1.272456 64 6.858437 1.143073 128 7.524225 1.074889 256 8.317139 1.039642 512 9.189112 1.021012 1024 10.112867 1.011287 2048 11.066819 1.006075 4096 12.038827 1.003236 8192 13.022343 1.001719 16384 14.013163 1.000940 32768 15.007320 1.000488 65536 16.004213 1.000263 131072 17.002441 1.000144 262144 18.001348 1.000075 524288 19.000775 1.000041 1048576 20.000428 1.000021

Ahora, ¿es este un argumento para que el algoritmo ideal sea log2 (n) en el caso promedio ? Quizás. Ciertamente no es así en el peor de los casos.

Además, no tiene que elegir los elementos log2 (n) a la vez. Puede seleccionar 2 y verificar la igualdad (pero en el caso degenerado, no encontrará la duplicación en absoluto), o verificar cualquier otro número mayor para la duplicación. En este punto, todos los algoritmos que seleccionan elementos y verifican la duplicación son idénticos, variando solo en la cantidad que elijan y en cómo identifican la duplicación.