ventajas posicion online método metodo falsa ejemplos ejemplo desventajas definicion bisección biseccion algorithm logic

algorithm - posicion - Encuentra el intervalo más grande que tiene todos sus miembros en la lista en O(n)



metodo de falsa posicion (10)

Me lo preguntaron en una entrevista. Dada una lista de enteros, ¿cómo podemos encontrar el intervalo más grande que tiene todos sus miembros en la lista dada?

Por ejemplo, la lista dada 1,3,5,7,4,6,10 entonces la respuesta sería [3, 7]. Porque tiene todos los elementos entre 3 y 7.

Traté de responder, pero no estaba convincente. El enfoque que tomé fue primero ordenar la lista y luego verificar el intervalo más grande. Pero me pidieron que lo hiciera en O(n) .

Aquí hay una solución similar a la de Grigor. Dos diferencias principales son que esta solución almacena la longitud del conjunto secuencial en lugar de otros índices y que esto elimina la necesidad de la última iteración del conjunto hash.

  1. Iteramos sobre la matriz

    • Cree un hashmap buscando y actualizando los puntos finales establecidos adyacentes:

      Clave : los valores de la matriz

      Valor : cuando la clave es un punto final de un conjunto secuencial, almacene la longitud de ese conjunto. De lo contrario, manténgalo verdadero así que solo considera las cosas una vez.

    • Si el tamaño del conjunto actual es más largo, actualice el tamaño del conjunto más largo y el inicio del conjunto más largo.

Aquí hay una implementación de JavaScript para mayor claridad, así como un fiddle para verlo en acción:

var array = [1,3,5,7,4,6,10]; //Make a hash of the numbers - O(n) assuming O(1) insertion var longestSetStart; var longestSetSize = 0; var objArray = {}; for(var i = 0; i < array.length; i++){ var num = array[i]; if(!objArray[num]){//Only consider numbers once objArray[num] = 1;//Initialize to 1 item in the set by default //Get the updated start and end of the current set var currentSetStart = num;//Starting index of the current set var currentSetEnd = num;//Ending index of the current set //Get the updated start of the set var leftSetSize = objArray[num - 1]; if(leftSetSize){ currentSetStart = num - leftSetSize; } //Get the updated end of the set var rightSetSize = objArray[num + 1]; if(rightSetSize){ currentSetEnd = num + rightSetSize; } //Update the endpoints var currentSetSize = currentSetEnd - currentSetStart + 1; objArray[currentSetStart] = currentSetSize; objArray[currentSetEnd] = currentSetSize; //Update if longest set if(currentSetSize > longestSetSize){ longestSetSize = currentSetSize; longestSetStart = currentSetStart; } } } var longestSetEnd = longestSetStart + longestSetSize - 1;

Conozco una solución basada en hash y programación dinámica. Deje f (x) ser la función hash. El truco es el valor de la tabla hash. Considere el intervalo más largo contenido en la lista, que comienza o termina con x . Entonces h [ f (x) ] = y , donde y es el otro extremo de ese intervalo . Tenga en cuenta que la duración de ese intervalo será abs ( x - y ) + 1 . La descripción del algoritmo aclarará por qué almacenar ese valor.

Mueva sobre la lista. Deje que sea el índice actual, x : = lista [ i ] - número actual. Ahora

1. si h [ f (x) ] no está vacío, entonces nos hemos encontrado con el número x anterior. Nada que hacer, continúa.

2. Compruebe h [ f (x-1) ] y h [ f (x + 1) ] .

2.1. Si ambos no están vacíos, eso significa que ya hemos cumplido x-1 y x + 1 , y sabemos algunos intervalos [ a..x-1 ] y [ x + 1..b ] que ya hemos se reunió en la lista. Lo sabemos porque a = h [ f (x-1) ] y b = h [ f (x + 1) ] por definición de h . Ahora cuando tenemos x , significa que ahora hemos cumplido con todo el intervalo [ a, b ] , así que actualizamos los valores de la siguiente manera: h [ f (a) ]: = b y h [ f (b) ]: = a .
También configure h [ f (x) ] con algún valor (digamos x , no para impactar la respuesta), solo para que la próxima vez que encontremos x en la lista, lo ignoremos. x ya ha hecho su trabajo.

2.2. Si solo se establece uno de ellos, digamos h [ f (x-1) ] = a , eso significa que ya hemos encontrado algún intervalo [ a..x-1 ] , y ahora está extendido con x . La actualización será h [ f (a) ]: = x y h [ f (x) ]: = a .

2.3. Si ninguno de ellos está configurado, eso significa que no hemos encontrado ni x-1 , ni x + 1 , y el mayor intervalo que contiene x que ya hemos encontrado es el único [ x ] . Así que configure h [ f (x) ]: = x .

Finalmente, para obtener la respuesta, pase la lista completa y tome el máximo de abs ( x - h [ f (x) ]) + 1 para todo x .

Creo que los habría ordenado en listas de enteros consecutivos (asumiendo que cada número puede aparecer solo una vez)

tomar el primer número

si el número 1 es menor que o 1 más que un número en una lista existente?

sí: pre / post pend lista existente

no: crea una nueva lista comenzando con el número actual

si hay más números, volver al principio

mostrar la lista más larga

Descargo de responsabilidad: dado que la solución se basa en hashtables, se esperan los tiempos de ejecución, no el peor de los casos.

Esta solución O (n) depende de que los enteros sean únicos. Si no son únicos, haga un hashset con inserción de O (1) y búsqueda de membresía, y simplemente saltee los números ya encontrados, a medida que avanza en la lista.

  1. Realice un hashmap de búsqueda (O) O (1) donde los valores son los comienzos de los rangos, y las claves son los números que se ajustan al final de esos rangos. Para un valor v y una clave k, esto significa que el rango que comienza desde v y termina con k-1 inclusive se ubica en la tecla k.

  2. Repase la lista de números. Para cada número n compruebe si el mapa tiene un valor v en la tecla n. Esto corresponde a que hay un rango que comienza desde v que permitiría n al final. Si lo hay, mueva v a la tecla n + 1 y elimine la entrada en la tecla n. Si no hay ningún rango, inserte n en la tecla n + 1.

  3. Como los números son únicos, ninguno de los rangos se superpone al final, pero puede haber algunos contiguos. Ejecutar a través de los pares clave / valor del mapa. Para cada clave k y valor v, si el mapa tiene un valor v1 en la clave k1 = v, significa que hay un rango de v1 a k-1. Inserte v1 en k, y elimine la entrada k1 / v1.

  4. Revise las entradas k / v del mapa para encontrar el rango más grande [v, k-1] de tamaño kv, utilizando un máximo de ejecución.

Para tu ejemplo:

setup: l = [1,3,5,7,4,6,10] m = {} iteration: process 1 : m = {2->1} process 3 : m = {2->1, 4->3} process 5 : m = {2->1, 4->3, 6->5} process 7 : m = {2->1, 4->3, 6->5, 8->7} process 4 : m = {2->1, 5->3, 6->5, 8->7} process 6 : m = {2->1, 5->3, 7->5, 8->7} process 10 : m = {2->1, 5->3, 7->5, 8->7, 11->10} concatenation of contiguous ranges: initial: m = {2->1, 5->3, 7->5, 8->7, 11->10} first concatenation: m = {2->1, 7->3, 8->7, 11->10}, k=7, v=5, k1=5, v1=3 second concatenation: m = {2->1, 8->3, 11->10}, k=8, v=7, k1=7, v1=3 result: largest range : [3,7] of size 5

El truco es pensar en los elementos como un conjunto en lugar de una lista. Esto le permite identificar elementos que están al principio o al final de los rangos contiguos, porque un conjunto le permite verificar si está presente el elemento 1 o el elemento + 1. Con eso, puedes resolver el problema en tiempo y espacio lineal.

Pseudo-código:

  • Enumere los elementos en el conjunto, buscando los que están al principio de un rango (x inicia un rango cuando x-1 no está en el conjunto).
  • Para cada valor que sea el inicio de un rango, escanee hacia arriba hasta encontrar el valor correspondiente del final del rango (x termina un rango cuando x + 1 no está en el conjunto). Esto le proporciona todos los rangos contiguos relevantes.
  • Devuelve el rango contiguo cuyo extremo estuvo más alejado de su inicio.

C # Code:

static Tuple<int, int> FindLargestContiguousRange(this IEnumerable<int> items) { var itemSet = new HashSet<int>(items); // find contiguous ranges by identifying their starts and scanning for ends var ranges = from item in itemSet // is the item at the start of a contiguous range? where !itemSet.Contains(item-1) // find the end by scanning upward as long as we stay in the set let end = Enumerable.Range(item, itemSet.Count) .TakeWhile(itemSet.Contains) .Last() // represent the contiguous range as a tuple select Tuple.Create(item, end); // return the widest contiguous range that was found return ranges.MaxBy(e => e.Item2 - e.Item1); }

nota: MaxBy es de MoreLinq

Pruebas

Pequeño control de cordura:

new[] {3,6,4,1,8,5}.FindLargestContiguousRange().Dump(); // prints (3, 6)

Gran lista contigua:

var zeroToTenMillion = Enumerable.Range(0, (int)Math.Pow(10, 7)+1); zeroToTenMillion.FindLargestContiguousRange().Dump(); // prints (0, 10000000) after ~1 seconds

Gran lista fragmentada:

var tenMillionEvens = Enumerable.Range(0, (int)Math.Pow(10, 7)).Select(e => e*2); var evensWithAFewOdds = tenMillionEvens.Concat(new[] {501, 503, 505}); evensWithAFewOdds.FindLargestContiguousRange().Dump(); // prints (500, 506) after ~3 seconds

Complejidad

Este algoritmo requiere O (N) tiempo y O (N) espacio, donde N es el número de elementos en la lista, suponiendo que las operaciones establecidas son tiempo constante.

Tenga en cuenta que si el conjunto se da como una entrada, en lugar de ser construido por el algoritmo, solo necesitaríamos O (1) espacio.

(Algunos comentarios dicen que este es un tiempo cuadrático. Creo que asumieron todos los ítems, en lugar de solo los ítems al comienzo de los rangos, los escaneos activados. Eso sí sería cuadrático, si el algoritmo funcionara de esa manera).

Eso sería lineal teniendo en cuenta los diccionarios construidos con tablas de hash O (1) promedio.

L = [1,3,5,7,4,6,10] a_to_b = {} b_to_a = {} for i in L: if i+1 in a_to_b and i-1 in b_to_a: new_a = b_to_a[i-1] new_b = a_to_b[i+1] a_to_b[new_a] = new_b b_to_a[new_b] = new_a continue if i+1 in a_to_b: a_to_b[i] = a_to_b[i+1] b_to_a[a_to_b[i]] = i if i-1 in b_to_a: b_to_a[i] = b_to_a[i-1] a_to_b[b_to_a[i]] = i if not (i+1 in a_to_b or i-1 in b_to_a): a_to_b[i] = i b_to_a[i] = i max_a_b = max_a = max_b = 0 for a,b in a_to_b.iteritems(): if b-a > max_a_b: max_a = a max_b = b max_a_b = b-a print max_a, max_b

Puede intercambiar espacio para obtener esto en tiempo lineal.

  1. Escanee la lista de los valores más pequeños y más grandes, S y L.
  2. Utilice una matriz de booleanos o un vector de bits, A, lo suficientemente grande como para contener (L - S + 1) entradas.
  3. Repase nuevamente la lista, estableciendo el elemento apropiado de A en verdadero cuando lo vea.
  4. Ahora, A está ordenado. Pase por A y encuentre el conjunto consecutivo más grande de valores verdaderos.

Los primeros pasos son lineales en su lista. El último es lineal en el tamaño de A, que puede ser grande en relación con su lista si tiene solo unos pocos valores que están muy separados. Pero, dado que se trata de enteros, A está limitado.

Si la ordenación no es deseable, puede usar una combinación de mapa hash y estructura de datos Disjoint-set .

Para cada elemento de la lista, cree un nodo e insértelo en el hash map con key = value del elemento. A continuación, consulte el mapa hash para value + 1 y value-1. Si se encuentra algo, combine el nodo actual con el conjunto (s) donde pertenecen los nodos adyacentes. Cuando termine con la lista, el conjunto más grande corresponde al intervalo más grande.

La complejidad del tiempo es O (N * α (N)) donde α (N) es la función inversa de Ackermann.

Editar: En realidad, el conjunto disjunto es demasiado poderoso para esta simple tarea. La solución de Grigor Gevorgyan no la usa. Entonces es más simple y más eficiente.

HashSet una solución muy simple usando un HashSet . Como contains y remove operaciones O (1), puede simplemente crear un nuevo intervalo a partir de un elemento de conjunto aleatorio y ''expandir'' el intervalo hasta descubrir su tamaño completo, eliminando elementos del conjunto a medida que avanza. La eliminación es clave, porque esto es lo que evita que ''repita'' cualquier intervalo.

Puede ser útil pensar de esta manera: la lista tiene K intervalos, cuyos tamaños se suman a N. Su tarea, entonces, es descubrir cuáles son estos intervalos, sin repetir ningún intervalo o elemento. Esta es la razón por la que HashSet es perfecto para el trabajo: puede eliminar elementos del conjunto de manera eficiente a medida que expande sus intervalos. Entonces, todo lo que necesita hacer es realizar un seguimiento del mayor intervalo a medida que avanza.

  1. Ponga la lista en un HashSet
  2. Si bien el conjunto no está vacío:
    1. eliminar un elemento al azar del conjunto
    2. Definir un nuevo intervalo a partir de ese elemento
    3. Expanda el intervalo de la siguiente manera:
      1. Definir i = interval.start-1
      2. Mientras que el conjunto contiene i , elimine i del conjunto y disminuya tanto i como interval.start
      3. Repita el paso 2 en la otra dirección (expanda desde interval.end )
    4. Si el intervalo expandido es mayor que el intervalo anterior más grande, registre el nuevo intervalo como el intervalo más grande
  3. Devuelve el intervalo más grande

Aquí está la solución en Java:

public class BiggestInterval { static class Interval { int start; int end; public Interval(int base) { this(base,base); } public Interval(int start, int end) { this.start = start; this.end = end; } public int size() { return 1 + end - start; } @Override public String toString() { return "[" + start + "," + end + "]"; } } /** * @param args */ public static void main(String[] args) { System.out.println(biggestInterval(Arrays.asList(1,3,5,7,4,6,10))); } public static Interval biggestInterval(List<Integer> list) { HashSet<Integer> set = new HashSet<Integer>(list); Interval largest = null; while(set.size() > 0) { Integer item = set.iterator().next(); set.remove(item); Interval interval = new Interval(item); while(set.remove(interval.start-1)) { interval.start--; } while(set.remove(interval.end+1)) { interval.end++; } if (largest == null || interval.size() > largest.size()) { largest = interval; } } return largest; } }

1 idea : bueno, creo que debes ordenar la lista de todos modos, pero no puedes combinarla o ordenarla rápidamente. Pero si tiene memoria, podría usar la idea del conteo de ordenamiento para enteros.

Así que puedes crear una matriz de 0 y 1, de 0 a un máximo de valor int, luego llenarlo con unos si tienes valor y luego encontrar la matriz continua máxima

2 idea : crear un diccionario de valores, encontrar el mínimo y máximo - todas las operaciones O (N):

dict = {1: 1, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 10: 10} min = 1 max = 10

luego, vaya como i in range(min, max) encuentre el subconjunto continuo más largo

>>> d = [1, 3, 5, 7, 4, 6, 10] >>> s = set(d) >>> mind = min(d) >>> maxd = max(d) >>> a, b, j = 0, 0, 0 >>> for i in range(mind, maxd): if i not in s: if (b - a) < (i - j - 1): a, b = j, i - 1 j = i + 1 >>> a, b (3, 7)

pero esto podría ser lento para listas dispersas como [1, 9000, 100000]

EDIT : basado en la gran respuesta de Grigor Gevorgyan , aquí está el código para la solución de diccionario O (N) en Python (¡Me encanta su simplicidad!)

l = [1, 3, 5, 7, 4, 6, 10] d = {x:None for x in l} print d for (k, v) in d.iteritems(): if v is not None: continue a, b = d.get(k - 1), d.get(k + 1) if a is not None and b is not None: d[k], d[a], d[b] = k, b, a elif a is not None: d[a], d[k] = k, a elif b is not None: d[b], d[k] = k, b else: d[k] = k print d m = max(d, key=lambda x: d[x] - x) print m, d[m]

salida:

{1: None, 3: None, 4: None, 5: None, 6: None, 7: None, 10: None} {1: 1, 3: None, 4: None, 5: None, 6: None, 7: None, 10: None} {1: 1, 3: 3, 4: None, 5: None, 6: None, 7: None, 10: None} {1: 1, 3: 4, 4: 3, 5: None, 6: None, 7: None, 10: None} {1: 1, 3: 5, 4: 3, 5: 3, 6: None, 7: None, 10: None} {1: 1, 3: 6, 4: 3, 5: 3, 6: 3, 7: None, 10: None} {1: 1, 3: 7, 4: 3, 5: 3, 6: 3, 7: 3, 10: None} {1: 1, 3: 7, 4: 3, 5: 3, 6: 3, 7: 3, 10: 10} 3 7