Algoritmo para encontrar 2 elementos con la diferencia dada en una matriz

Question

Tengo una matriz de números reales, A. Tiene n + 1 elementos. Se sabe que hay al menos 2 elementos de la matriz, X e Y, tal que:

abs(x-y) <= (max(A)-min(A))/n 

Necesito crear un algoritmo para encontrar los 2 elementos (si hay más, cualquier pareja es bueno) en el tiempo O (n).

He estado intentando durante unas horas y estoy atascado, ¿alguna pista/sugerencia?

Answer 1

woo ¡Lo tengo! El truco está en el Pigeonhole Principle.

Bien ... piense en los números como puntos en una línea. Luego, min(A) y max(A) definen los puntos de inicio y fin de la línea, respectivamente. Ahora divida esa línea en n intervalos iguales de longitud (max(A)-min(A))/n. Como hay n+1 puntos, dos de ellos deben caer en uno de los intervalos.

Tenga en cuenta que no necesitamos confiar en la pregunta que nos dice que hay dos puntos que satisfacen el criterio. Hay siempre dos puntos que lo satisfacen.

Algoritmo en sí mismo: aquí puede usar una forma simplificada de clasificación de depósitos, ya que solo necesita un artículo por cubo (marque dos y listo).Primero bucle una vez a través de la matriz para obtener min(A) y max(A) y crear una matriz de enteros buckets[n] inicializada a un valor predeterminado, por ejemplo -1. A continuación, vaya para un segundo pase:

for (int i=0; i<len; i++) { 
    int bucket_num = find_bucket(array[i]); 
    if (bucket[bucket_num] == -1) 
     bucket[bucket_num] = i; 
    else 
     // found pair at (i, bucket[bucket_num]) 
} 

Dónde find_bucket(x) devuelve el resultado número entero redondeado hacia abajo de x/((max(A)-min(A))/n).

Answer 2

Repasemos el problema: estamos para encontrar dos elementos, tales como abs(x-y) <= c, donde c es una constante, que podemos encontrar en O(n) time. (De hecho, podemos calcular tanto max(A) como min(A) en tiempo lineal y solo asignar c=(max-min)/n).

Imaginemos que tenemos un conjunto de cubos, de modo que en unos primeros elementos de cubo 0<=x<c se colocan, en los segundos elementos de cubo c<=x<=2c se colocan, etc. Para cada elemento, podemos determinar su cubo para O(1) tiempo. Tenga en cuenta que la cantidad de cubos ocupados no será mayor que la cantidad de elementos en el conjunto.

Vamos a iterar la matriz y colocar cada elemento en su cubo. Si en el cubo lo vamos a colocar, ya hay otro elemento, entonces, acabamos de encontrar el par correcto de x y y!

Si hemos repetido todo el conjunto y cada elemento ha caído en su propio cubo, ¡no se preocupe! Iterar los cubos ahora (no hay más de n cubos, como hemos dicho anteriormente) y para cada elemento de cubeta x, si en el cubo siguiente y elemento es tal que abs(x-y)<=c, entonces hemos encontrado la solución.

Si repetimos todos los intervalos y no encontramos los elementos adecuados, no hay solución. Dios mío, realmente extrañé esas cosas de encasillamiento (ver the other answer).

Los cubos pueden implementarse como un mapa hash, donde cada cubo contiene un índice de matriz (el elemento de colocación en el cubo se verá así: buckets[ a[i]/c] = i). Calculamos c en O(n) vez, asignamos elementos a los segmentos en O(n)*O(1) el tiempo (O(1) es el acceso al mapa hash), recorre los segmentos en el tiempo O(n). Por lo tanto, todo el algoritmo es lineal.