Posiciones fuera de lugar
La misión
Problema
Unos estudiantes están en una fila, cada uno descrito por su estatura. Se suponía que debían formarse del más bajo al más alto. Cuenta las posiciones ocupadas por un estudiante cuya estatura difiere de la estatura que debería haber ahí. Las estaturas iguales son intercambiables, así que una posición con la estatura correcta nunca se cuenta.
Ejemplos
Input: heights = [1, 1, 4, 2, 1, 3]
Output: 3
Por qué: la fila correcta es 1 1 1 2 3 4, y tres posiciones no coinciden
Input: heights = [5, 4, 3, 2, 1]
Output: 4
Por qué: solo el estudiante del medio ya está, por casualidad, en su lugar correcto
Input: heights = [1, 2, 3]
Output: 0
Por qué: caso límite: una fila que ya es correcta no tiene nada fuera de lugar
Pistas
0 / 3
La pregunta compara la fila que recibiste con una fila que primero tienes que calcular, así que construye esa segunda fila antes de contar nada.
La fila objetivo son simplemente las mismas estaturas ordenadas de la más baja a la más alta, así que una copia ordenada de la entrada es exactamente lo que necesitas para comparar.
Ordena una copia de las estaturas y luego recorre ambas filas juntas, posición por posición, contando las posiciones donde las dos estaturas difieren. Trabaja con la copia, nunca con el original, o la comparación destruye justo lo que se está revisando.
- Tiempo objetivo
- O(n log n)
- Espacio objetivo
- O(n)
Solución
La fila objetivo es solo la entrada ordenada, así que toda la tarea consiste en producir esa copia y comparar posición por posición. Ordenar una copia en lugar de la propia entrada importa: ordenar in-place (sin memoria extra) sobrescribiría la fila que se está evaluando y el conteo siempre daría cero. Comparar estaturas en lugar de estudiantes basta, porque dos estudiantes de igual estatura son intercambiables y una posición con la estatura correcta está bien sin importar quién esté ahí. El tiempo es O(n log n) por el ordenamiento (sorting) y el espacio es O(n) por la copia.
def count_out_of_place(heights):
target = sorted(heights) # a COPY, so the original line survives
mismatches = 0
for standing, expected in zip(heights, target):
if standing != expected: # this position holds the wrong height
mismatches += 1
return mismatches
print(count_out_of_place([1, 1, 4, 2, 1, 3])) # -> 3
print(count_out_of_place([5, 4, 3, 2, 1])) # -> 4
print(count_out_of_place([1, 2, 3])) # -> 0¿Lo que te frena es la idea y no el código? Fundamentos del ordenamiento lo explica.