Dada una matriz, descubre el siguiente elemento más pequeño para cada elemento

Dada una matriz, encuentre el siguiente elemento más pequeño en la matriz para cada elemento sin cambiar el orden original de los elementos.

Por ejemplo, supongamos que la matriz dada es 4,2,1,5,3.

La matriz resultante sería 2,1, -1,3, -1.

Me hicieron esta pregunta en una entrevista, pero no se me ocurrió una solución mejor que la solución trivial O (n ^ 2). Cualquier enfoque que se me ocurra, es decir, hacer un árbol de búsqueda binario o clasificar el conjunto, distorsionará el orden original de los elementos y, por lo tanto, dará lugar a un resultado incorrecto.

Cualquier ayuda sería muy apreciada.

Algoritmo O (N)

  1. Inicialice la matriz de salida en -1.
  2. Cree una stack vacía de índices de elementos que hemos visitado en la matriz de entrada, pero aún no conocemos la respuesta en la matriz de salida.
  3. Iterar sobre cada elemento en la matriz de entrada:
    1. ¿Es más pequeño que el elemento indexado por la parte superior de la stack?
      1. Sí. Es el primer elemento de este tipo. Complete el elemento correspondiente en nuestra matriz de salida, elimine el elemento de la stack y vuelva a intentarlo hasta que la stack esté vacía o la respuesta sea no.
      2. No. Continúa a 3.2.
    2. Agregue este índice a la stack. Continuar la iteración desde 3.

Implementación de Python

 def find_next_smaller_elements(xs): ys=[-1 for x in xs] stack=[] for i,x in enumerate(xs): while len(stack)>0 and x>> find_next_smaller_elements([4,2,1,5,3]) [2, 1, -1, 3, -1] >>> find_next_smaller_elements([1,2,3,4,5]) [-1, -1, -1, -1, -1] >>> find_next_smaller_elements([5,4,3,2,1]) [4, 3, 2, 1, -1] >>> find_next_smaller_elements([1,3,5,4,2]) [-1, 2, 4, 2, -1] >>> find_next_smaller_elements([6,4,2]) [4, 2, -1] 

Explicación

Cómo funciona

Esto funciona porque cada vez que agregamos un elemento a la stack, sabemos que su valor es mayor o igual a cada elemento de la stack. Cuando visitamos un elemento en la matriz, sabemos que si es más bajo que cualquier elemento en la stack, debe ser más bajo que el último elemento en la stack, porque el último elemento debe ser el más grande. Así que no necesitamos hacer ningún tipo de búsqueda en la stack, solo podemos considerar el último elemento.

Nota: Puede omitir el paso de inicialización siempre y cuando agregue un último paso para vaciar la stack y use cada índice restante para establecer el elemento de matriz de salida correspondiente en -1. Simplemente es más fácil en Python inicializarlo en -1s al crearlo.

Complejidad del tiempo

Esto es O (N). El ciclo principal claramente visita cada índice una vez. Cada índice se agrega a la stack exactamente una vez y se elimina como máximo una vez.

Resolviendo como una pregunta de entrevista

Este tipo de pregunta puede ser bastante intimidante en una entrevista, pero me gustaría señalar que (con suerte) un entrevistador no va a esperar que la solución salga de su mente completamente formada. Háblales a través de tu proceso de pensamiento. El mío fue algo como esto:

  • ¿Existe alguna relación entre las posiciones de los números y su próximo número más pequeño en la matriz? ¿Conocer algunos de ellos limita lo que otros posiblemente sean?
  • Si estuviera frente a una pizarra, probablemente dibujaría la matriz de ejemplo y dibujaría líneas entre los elementos. También podría dibujarlos como un gráfico de barras 2D: el eje horizontal es la posición en la matriz de entrada y el eje vertical es el valor.
  • Tenía la corazonada de que esto mostraría un patrón, pero no papel a mano. Creo que el diagtwig lo haría obvio. Al pensarlo cuidadosamente, pude ver que las líneas no se superponían arbitrariamente, sino que solo anidaban.
  • Alrededor de este punto, se me ocurrió que esto es increíblemente similar al algoritmo que Python usa internamente para transformar la indentación en tokens virtuales INDENT y DEDENT, sobre los cuales había leído antes. Consulte “¿Cómo analiza el comstackdor la sangría?” en esta página: http://www.secnetix.de/olli/Python/block_indentation.hawk Sin embargo, no fue hasta que realmente resolví un algoritmo que seguí este pensamiento y determiné que de hecho era el mismo , así que no creo que haya ayudado demasiado. Aún así, si puede ver una similitud con algún otro problema, probablemente sea una buena idea mencionarlo, y decir cómo es similar y cómo es diferente.
  • A partir de aquí, la forma general del algoritmo basado en la stack se hizo evidente, pero aún necesitaba pensar un poco más para asegurarme de que funcionaría bien para aquellos elementos que no tienen un elemento posterior más pequeño.

Incluso si no se le ocurre un algoritmo de trabajo, intente que su entrevistador vea lo que está pensando. A menudo es el proceso de pensamiento más que la respuesta lo que les interesa. Para un problema difícil, no encontrar la mejor solución, pero mostrar una idea del problema puede ser mejor que conocer una respuesta enlatada, pero no poder darle mucha análisis.

Comience a hacer una BST, comenzando desde el extremo de la matriz. Para cada valor ‘v’, la respuesta sería el último nodo “Derecho” que tomó en su camino hacia la inserción de ‘v’, del cual puede hacer un seguimiento fácilmente en versión recursiva o iterativa.

ACTUALIZAR:

Siguiendo sus requisitos, puede abordar esto de forma lineal:

Si cada elemento siguiente es más pequeño que el elemento actual (por ejemplo, 6 5 4 3 2 1), puede procesarlo linealmente sin requerir memoria adicional. El caso interesante surge cuando comienzas a obtener elementos mezclados (por ejemplo, 4 2 1 5 3), en cuyo caso debes recordar su orden siempre y cuando no consigas sus ‘contrapartes más pequeñas’. Un enfoque simple basado en la stack es el siguiente:

Presione el primer elemento (a [0]) en una stack.

Para cada elemento siguiente a [i], echas un vistazo a la stack y si el valor (peek ()) es mayor que el que está a mano a [i], tienes tu próximo número más pequeño para ese elemento de stack (peek ()) { y siga apareciendo los elementos siempre que peek ()> a [i]}. Pop out e imprimir / almacenar el valor correspondiente. de lo contrario, simplemente devuelve tu a [i] a la stack.

Al final, la stack contendrá aquellos elementos que nunca tuvieron un valor más pequeño que ellos (a su derecha). Puede completar -1 para ellos en su outpput.

por ejemplo, A = [4, 2, 1, 5, 3];

 stack: 4 a[i] = 2, Pop 4, Push 2 (you got result for 4) stack: 2 a[i] = 1, Pop 2, Push 1 (you got result for 2) stack: 1 a[i] = 5 stack: 1 5 a[i] = 3, Pop 5, Push 3 (you got result for 5) stack: 1 3 1,3 don't have any counterparts for them. so store -1 for them. 

Asumiendo que se refería al primer elemento siguiente que es más bajo que el elemento actual, aquí hay 2 soluciones:

  1. Use la segmentación sqrt(N) . Divida la matriz en segmentos sqrt(N) con la longitud de cada segmento siendo sqrt(N) . Para cada segmento, calcule su ‘elemento mínimo usando un bucle. De esta forma, ha precalculado el elemento mínimo de cada segmento en O(N) . Ahora, para cada elemento, el siguiente elemento inferior puede estar en el mismo segmento que ese o en cualquiera de los segmentos subsiguientes. Por lo tanto, primero verifique todos los elementos siguientes en el segmento actual. Si todos son más grandes, recorra todos los segmentos subsiguientes para descubrir cuál tiene un elemento más bajo que el elemento actual. Si no puede encontrar ninguno, el resultado sería -1 . De lo contrario, verifique cada elemento de ese segmento para descubrir cuál es el primer elemento más bajo que el elemento actual. En general, la complejidad del algoritmo es O(N*sqrt(N)) o O(N^1.5) .

Puede lograr O(NlgN) usando un árbol de segmentos con un enfoque similar.

  1. Ordene primero la matriz ascendente (manteniendo la posición original de los elementos como datos satelitales). Ahora, suponiendo que cada elemento de la matriz es distinto, para cada elemento, necesitaremos encontrar la posición original más baja en el lado izquierdo de ese elemento. Es un problema clásico de RMQ (Range Min Query) y se puede resolver de muchas maneras, incluida una O(N) . Como primero debemos ordenar, la complejidad general es O(NlogN) . Puede obtener más información sobre RMQ en un tutorial de TopCoder .

Por alguna razón, me resulta más fácil razonar sobre “elemento anterior más pequeño”, también conocido como “todos los elementos más pequeños más cercanos” . Por lo tanto, aplicado hacia atrás da el “próximo más pequeño”.

Para el registro, una implementación de Python en O (n) tiempo, O (1) espacio (es decir, sin stack), que admite valores negativos en la matriz:

 def next_smaller(l): """ Return positions of next smaller items """ res = [None] * len(l) for i in range(len(l)-2,-1,-1): j=i+1 while j is not None and (l[j] > l[i]): j = res[j] res[i] = j return res def next_smaller_elements(l): """ Return next smaller items themselves """ res = next_smaller(l) return [l[i] if i is not None else None for i in res] 

Aquí está el código de javascript. Este video explica el Algo mejor

 function findNextSmallerElem(source){ let length = source.length; let outPut = [...Array(length)].map(() => -1); let stack = []; for(let i = 0 ; i < length ; i++){ let stackTopVal = stack[ stack.length - 1] && stack[ stack.length - 1].val; // If stack is empty or current elem is greater than stack top if(!stack.length || source[i] > stackTopVal ){ stack.push({ val: source[i], ind: i} ); } else { // While stacktop is greater than current elem , keep popping while( source[i] < (stack[ stack.length - 1] && stack[ stack.length - 1].val) ){ outPut[stack.pop().ind] = source[i]; } stack.push({ val: source[i], ind: i} ); } } return outPut; } 

Salida -

 findNextSmallerElem([98,23,54,12,20,7,27]) [23, 12, 12, 7, 7, -1, -1] 

Aquí hay una observación que creo que se puede convertir en una solución O (n log n). Supongamos que tiene la respuesta para los últimos k elementos de la matriz. ¿Qué necesitarías para calcular el valor del elemento justo antes de esto? Puede pensar en los últimos elementos k como divididos en una serie de rangos, cada uno de los cuales comienza en algún elemento y continúa hacia adelante hasta que golpea un elemento más pequeño. Estos rangos deben estar en orden descendente, por lo que podría pensar en hacer una búsqueda binaria sobre ellos para encontrar el primer intervalo más pequeño que ese elemento. Luego puede actualizar los rangos para factorizar este nuevo elemento.

Ahora, ¿cuál es la mejor manera de representar esto? La mejor forma en que he pensado es usar un árbol desplegable cuyas claves son los elementos que definen estos rangos y cuyos valores son el índice en el que comienzan. A continuación, puede amortizar en el tiempo O (log n) hacer una búsqueda predecesora para encontrar el predecesor del elemento actual. Esto encuentra que el primer valor es más pequeño que el actual. Luego, en el tiempo O (log n) amortizado, inserte el elemento actual en el árbol. Esto representa definir un nuevo rango desde ese elemento hacia adelante. Para descartar todos los rangos que esto reemplaza, entonces corta el hijo derecho del nuevo nodo, que debido a que este es un árbol desplegable está en la raíz, desde el árbol.

En general, esto hace O (n) iteraciones de un proceso O (log n) para O total (n lg n).

Aquí hay un algoritmo O (n) que usa DP (en realidad O (2n)):

 int n = array.length(); 

La matriz min [] registra el número mínimo encontrado desde el índice i hasta el final de la matriz.

 int[] min = new int[n]; min[n-1] = array[n-1]; for(int i=n-2; i>=0; i--) min[i] = Math.min(min[i+1],array[i]); 

Busque y compare a través de la matriz original y min [].

 int[] result = new int[n]; result[n-1] = -1; for(int i=0; i 

Aquí está la nueva solución para encontrar el "siguiente elemento más pequeño":

 int n = array.length(); int[] answer = new int[n]; answer[n-1] = -1; for(int i=0; i 
  All that is actually not required i think case 1: a,b answer : -a+b case 2: a,b,c answer : a-2b+c case 3: a,b,c,d answer : -a+3b-3c+d case 4 :a,b,c,d,e answer : a-4b+6c-4d+e . . . recognize the pattern in it? it is the pascal's triangle! 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 so it can be calculated using Nth row of pascal's triangle! with alternate + ans - for odd even levels! it is O(1) 

Puede resolver esto en O (n) tiempo de ejecución con O (n) complejidad espacial. Comience con una stack y continúe presionando los elementos hasta que encuentre arr [i] tal que el elemento arr [i]

Fragmento de código:

 vector findNext(vector values) { stack st; vector nextSmall(values.size(), -1); st.push(0); for (int i = 1; i < values.size(); i++) { while (!st.empty() && values[i] < values[st.top()]) { // change values[i] < values[st.top()] to values[i] > values[st.top()] to find the next greater element. nextSmall[st.top()] = i; st.pop(); } st.push(i); } return nextSmall; } 

Solución con O (1) complejidad del espacio y O (n) complejidad del tiempo.

 void replace_next_smallest(int a[], int n) { int ns = a[n - 1]; for (int i = n - 1; i >= 0; i--) { if (i == n - 1) { a[i] = -1; } else if (a[i] > ns) { int t = ns; ns = a[i]; a[i] = t; } else if (a[i] == ns) { a[i] = a[i + 1]; } else { ns = a[i]; a[i] = -1; } } }