Encontrar la mitad de la lista de tamaños desconocidos

En una entrevista reciente me preguntaron:Encontrar la mitad de la lista de tamaños desconocidos

Encuentra el elemento medio de una lista ordenada de longitud desconocida comenzando desde la primera posición.

me respondieron con esto:

tener 2 contadores de posición:

COUNTER1 Counter2

Incremento contador1 en 1 y 2. Cuando Counter2 por el contador 2 llega al final de la barra de la lista 1 se estar en el medio. Siento que esto no es eficiente porque estoy revisando nodos que ya he visto. De cualquier manera, ¿hay un algoritmo más eficiente?

Fuente

2011-10-21 segFault

Este es el tiempo 'O (N)' y el espacio 'O (1)'; Parece bastante bueno para mí. – PengOne

Si la longitud es desconocida, ¿qué operaciones están permitidas? ¿Es una lista enlazada? – Vlad

Estaba pensando que podrías hacer algo similar pero los mismos contadores, pero en lugar de saltar 2, salta una cantidad mayor. Salta la distancia del contador que está saltando por 1 y luego cuando alcances tu conteo de límites por uno. ¿Es esto mejor, inválido o defectuoso? – segFault

Suponiendo una lista vinculada, puede hacerlo mientras visita arbitrariamente el N de los elementos.

Para hacer 5/4 N:

iterar sobre la lista hasta llegar a la final, contando los artículos.
Coloque un anclaje en cada potencia del 2 ° elemento. Sigue los últimos 2 anclajes.
Iterar el anclaje anterior hasta el último hasta que llegue al centro de la lista.

Cuando llegue al final de la lista, el ancla anterior es anterior al punto medio, pero al menos hasta la mitad ya existe. Así que N para la iteración completa + a lo sumo 1/4 N para el ancla = 5/4 N.

Dejar caer los anclajes con mayor frecuencia, como en cada potencia de techo de 1,5^ª elemento, lo acerca al N como máximo necesario (a costa de rastrear más anclas, pero para cualquier X dada como paso de potencia, la memoria asintótica es constante).

Fuente

2011-10-21 00:37:15

Gran respuesta. No estoy seguro para qué es la búsqueda binaria; si se trata de una matriz, podemos hacerlo mucho mejor desde el principio. – davin

Me refiero a una matriz en la que no se conoce la longitud exacta, pero puede verificar si una posición dada excede la longitud. Tal vez sea un filtro de floración sin falsos positivos y 0..N insertado. Eliminaré ese caso ya que es muy extraño y trivial. –

@Strilanc Si encuentra una manera de hacer un filtro de floración sin falsos positivos, háganoslo saber. –

Suponiendo que puede detectar que está más allá del final de la lista y busca una posición arbitraria de manera eficiente dentro de la lista, puede seguir doblando la longitud presunta de la lista (supongamos que la longitud es 1, luego 2, luego 4 , ...) hasta que haya pasado el final de la lista, luego utilice una búsqueda binaria entre el último intento de valor menor que la longitud de la lista y el primer valor que excedió el final de la lista para encontrar el final real de la lista.

A continuación, buscar la posición END_OF_LIST/2.

esta manera, usted no tiene que visitar cada nodo.

Fuente

2011-10-21 00:18:02

¡Buena solución para una matriz! – kyun

Supongo que está discutiendo una lista enlazada. De hecho, su solución es excelente. Una alternativa sería simplemente atravesar la lista contando el número de elementos, y luego volver a comenzar desde el principio, atravesando la mitad de la cantidad contada. Ambos métodos terminan cruzando nodos 3n/2, por lo que no hay mucha diferencia.

Es posible que haya pequeñas ventajas de caché para cualquier método según la arquitectura; el primer método podría tener la ventaja de tener nodos en caché, lo que podría significar una recuperación más rápida si el caché es lo suficientemente grande antes de que los dos indicadores estén separados por dos. Alternativamente, la memoria caché puede obtener mejores bloques si recorremos la lista de una vez, en lugar de mantener dos punteros con vida.

Fuente

2011-10-21 00:18:49 davin

Técnicamente, podría hacer esto en un cruce si usaba memoria O (N) (suponiendo que esté utilizando una lista vinculada).

Recorre la lista y conviértela en una matriz (de punteros si esta es una lista vinculada).
Volver matriz [N/2]

Editar: A mi me gusta tu respuesta, aunque!

Fuente

2011-10-21 08:40:32 kyun

Suponiendo que la lista ordinaria en memoria vinculada que permite leer el siguiente elemento dado la referencia a los actuales varias veces (disclaimer, no se ha probado, pero la idea debería funcionar):

// assume non-empty list 
slow = fast = first; 
count = 0; 

while (fast) 
{ 
    fast = fast.next; 

    if (!fast) 
    break; 

    count++; 
    fast = fast.next; 

    if (fast) 
    count++; 

    slow = slow.next; 
} 

if (count % 2) 
    return slow.data; 
else 
    return (slow.data + slow.next.data)/2.0;

Un caso más difícil es cuando la "lista" no es una lista vinculada en la memoria, sino más bien una secuencia que puede leer en orden ordenado y qué leer cada elemento solo una vez para la que no tengo una buena solución.

Fuente

2016-04-08 23:51:06

Encontrar la mitad de la lista de tamaños desconocidos

Respuesta

Cuestiones relacionadas