Encuentra el elemento con la distancia más larga en una matriz determinada donde cada elemento aparece dos veces?

Question

Dada una matriz de int, cada int aparece exactamente DOS VECES en la matriz . Encuentre y devuelva el int tal que este par de int tenga la distancia máxima de entre sí en esta matriz.

p. Ej. [2, 1, 1, 3, 2, 3]

2: d = 5-1 = 4; 
1: d = 3-2 = 1; 
3: d = 6-4 = 2; 
return 2 

Mis ideas:

Uso HashMap, la clave es a[i], y el valor es el índice. Escanee el a[], ponga cada número en hash. Si un número es golpeado dos veces, use su índice menos el índice de números antiguos y use el resultado para actualizar el valor del elemento en hash.

Después de eso, escanear hash y devolver la llave con el elemento más grande (distancia). es O (n) en tiempo y espacio.

Como hacerlo en tiempo O (n) y O (1) el espacio?

Answer 1

¿Le gustaría tener la máxima distancia, así que supongo que el número se busca una mayor probabilidad de estar en el inicio y el fin. Esta es la razón por la que pasaría por encima de la matriz desde el inicio hasta el final al mismo tiempo.

[2, 1, 1, 3, 2, 3] 
Check if 2 == 3? 
Store a map of numbers and position: [2 => 1, 3 => 6] 
Check if 1 or 2 is in [2 => 1, 3 => 6] ? 

Lo sé, eso ni siquiera es pseudocódigo y no está completo, pero solo para dar a conocer la idea.

Answer 2

índice de Conjunto iLeft al primer elemento, el índice iRight al segundo elemento. Incremente el índice de iRight hasta que encuentre una copia del elemento de la izquierda o encuentre el final de la matriz. En el primer caso, recuerda la distancia.

Incremento iLeft. Comience a buscar desde nuevo iRight. El valor de inicio de iRight nunca disminuirá. código Delphi:

iLeft := 0; 
    iRight := 1; 

    while iRight < Len do begin //Len = array size 
    while (iRight < Len) and (A[iRight] <> A[iLeft]) do 
     Inc(iRight); //iRight++ 
    if iRight < Len then begin 
     BestNumber := A[iLeft]; 
     MaxDistance := iRight - iLeft; 
    end; 
    Inc(iLeft); //iLeft++ 
    iRight := iLeft + MaxDistance; 
    end; 

Answer 3

Este algoritmo es O (1) espacio (con algo de trampa), O (n) tiempo (promedio), necesita la matriz de origen para ser no-const y lo destruye al final. También limita los valores posibles en la matriz (se deben reservar tres bits de cada valor para el algoritmo).

La mitad de la respuesta ya está en la pregunta. Usa hashmap. Si un número es golpeado dos veces, use la diferencia de índice, actualice el mejor resultado hasta ahora y elimine este número del hashmap para liberar espacio. Para convertirlo en O (1) espacio, simplemente reutilice la matriz fuente. Convierta la matriz a hashmap en contexto.

Antes de pasar un elemento de matriz a la célula HashMap, recuerde su valor y posición. Después de esto, puede sobrescribirse de manera segura. Luego use este valor para calcular una nueva posición en el hashmap y sobrescribirlo. Los elementos se mezclan de esta manera hasta que se encuentra una celda vacía. Para continuar, seleccione cualquier elemento que no esté reordenado. Cuando se reordena todo, cada int pair es definitivamente golpeado dos veces, aquí tenemos un hashmap vacío y un mejor valor de resultado actualizado.

Un bit reservado se utiliza mientras que la conversión elementos de la matriz a las células HashMap. Al principio está despejado. Cuando se reordena un valor a la celda hashmap, este bit se establece. Si este bit no está configurado para el elemento sobreescrito, este elemento simplemente se procesa para ser procesado a continuación. Si este bit está configurado para que se sobrescriba el elemento, aquí hay un conflicto, elija el primer elemento no utilizado (con este bit no configurado) y sobrescríbalo en su lugar.

2 bits más reservados se utilizan para encadenar valores conflictivos. Codifican las posiciones donde la cadena se inicia/finaliza/continúa. (Es posible optimizar este algoritmo para que solo se necesiten 2 bits reservados ...)

Una celda hashmap debe contener estos 3 bits reservados, el índice del valor original y cierta información para identificar este elemento de forma exclusiva. Para que esto sea posible, una función hash debe ser reversible para que parte del valor pueda restaurarse dada su posición en la tabla. En el caso más simple, la función hash es solo ceil(log(n)) bits menos significativos. Valor de la tabla consta de 3 campos:

• 3 bits reservados
• 32 - 3 - (ceil(log(n))) bits de orden superior del valor original
• ceil(log(n)) bits para la posición de los elementos de la matriz original

Complejidad de tiempo es O (n) solo en promedio; la complejidad del peor caso es O (n^2).

Otra variante de este algoritmo es transformar la matriz a hashmap secuencialmente: en cada paso m teniendo 2^m primeros elementos de la matriz convertidos a hashmap. Algunas matrices de tamaño constante se pueden intercalar con el hashmap para mejorar el rendimiento cuando m es bajo. Cuando m es alto, debe haber suficientes pares int, que ya están procesados ​​y ya no necesitan espacio.

Answer 4

No hay forma de hacerlo en el tiempo O (n) y en el espacio O (1).