Básicamente, la solución radica en el uso inteligente de la búsqueda binaria.
Así que intentaré explicarlo a través de un ejemplo:
Supongamos que tiene una matriz de números [4,3,2,5,6,1] y desea encontrar el arr_low. Entonces, la solución de fuerza bruta es atravesar el conjunto completo una vez y contar el número de números en el conjunto que son mayores que el número dado. La complejidad temporal de esta solución es O (n ^ 2) .
Así que ahora queremos hacerlo mejor que n ^ 2. Como podemos ver, el valor arr_low del último número siempre será cero, por lo que es mejor comenzar en orden inverso.
- Dada una matriz de entrada de enteros de tamaño n, y una matriz de consulta de enteros de tamaño k, ¿cómo encuentro la ventana más pequeña de la matriz de entrada que contiene todos los elementos de la matriz de consulta, preservando el orden?
- ¿Cómo se preparó para su entrevista de desarrollador Java con experiencia?
- ¿Qué se supone que debo hacer para resolver este ejercicio de programación (ver los detalles)?
- ¿Cuánto tiempo pasaste preparándote para las entrevistas de Google? ¿Todos los que se metieron en Facebook, Google, etc. realmente son tan buenos para resolver o entender cada algoritmo o problema clásico?
- ¿Por qué los entrevistadores hacen preguntas fuera del alcance / experiencia?
Ahora, una cosa a notar es que cuando comenzamos en reversa, el valor arr_low de un número dado es arr_low del número más bajo mayor que el número dado en la matriz recorrida hasta ahora.
Teniendo esto en cuenta, atravesaremos y crearemos una matriz auxiliar que mantendrá los números recorridos hasta ahora en un orden ordenado junto con el valor arr_low. Llamemos a la matriz auxiliar como aux.
Ahora, al recorrer en orden inverso, colocaremos el elemento en el auxiliar en el orden ordenado (Hecho de la misma manera que en Ordenar por inserción). La inserción en aux llevará tiempo O (log n) . Ahora, para cada elemento, necesitamos encontrar el elemento más alto más bajo que el elemento dado en el auxiliar (que por cierto ahora está ordenado y se puede hacer en tiempo O (log n) ) y colocar el elemento junto con el nuevo valor arr_low en el aux.
Entonces, la complejidad del tiempo neto es O (n * (log n + log n)), es decir, O (2nlogn), es decir, O (nlogn). La complejidad del espacio es O (N).
Lazo 1
arr: 4, 3, 2, 5, 6, 1
puntero a 1 (último elemento)
aux:
resultado: 0
Debido a que ningún elemento puede ser menor que el último elemento, arr_low es cero para él.
Lazo 2
arr: 4, 3, 2, 5, 6, 1
aux: (1,0)
resultado: 1,0
Búsqueda binaria para un número menor que 6, así que obtenga cero
Lazo 3
arr: 4, 3, 2, 5, 6, 1
Aux: (1,0) (6,0)
resultado: 1,1,0
La búsqueda binaria para un número mayor que 5 obtenemos (6,0) por lo que es arr_low será 0 + 1 = 1
Lazo 4
arr: 4, 3, 2, 5, 6, 1
Aux: (1,0) (5,1) (6,0)
resultado: 1,1,1,0
Lazo 5
arr: 4, 3, 2, 5, 6, 1
Aux: (1,0) (2,2) (5,1) (6,0)
resultado: 2,1,1,1,0
Lazo 6
arr: 4, 3, 2, 5, 6, 1
Aux: (1,0) (2,2) (3,2) (5,1) (6,0)
resultado: 3,2,1,1,0,0
Entonces el resultado neto es [3,2,1,1,1,0].