Saltar al contenido

Posiciones fuera de lugar

Fácil#sorting#pairwise-comparison~15 min

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

Tiempo objetivo
O(n log n)
Espacio objetivo
O(n)

¿Lo que te frena es la idea y no el código? Fundamentos del ordenamiento lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio