Pular para o conteúdo

Posições fora do lugar

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

A missão

Problema

Alunos estão em fila, cada um descrito por uma altura. Eles deveriam estar alinhados do mais baixo para o mais alto. Conte as posições ocupadas por um aluno cuja altura difere da altura que deveria estar ali. Alturas iguais são intercambiáveis, então uma posição com a altura certa nunca é contada.

Exemplos

Input:  heights = [1, 1, 4, 2, 1, 3]
Output: 3
Por quê: a fila correta é 1 1 1 2 3 4, e três posições divergem
Input:  heights = [5, 4, 3, 2, 1]
Output: 4
Por quê: só o aluno do meio, por acaso, já está no lugar certo
Input:  heights = [1, 2, 3]
Output: 0
Por quê: edge case: uma fila que já está correta não tem nada fora do lugar

Dicas

0 / 3

Tempo-alvo
O(n log n)
Espaço-alvo
O(n)

Travou na ideia, e não no código? O básico de ordenação explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado