Posições fora do lugar
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
A pergunta compara a fila que você recebeu com uma fila que você precisa descobrir antes, então monte essa segunda fila antes de contar qualquer coisa.
A fila alvo é simplesmente as mesmas alturas organizadas da mais baixa para a mais alta, então uma cópia ordenada da entrada é exatamente o que você precisa para comparar.
Ordene uma cópia das alturas e depois percorra as duas filas juntas, posição por posição, contando as posições em que as duas alturas diferem. Compare a cópia, nunca o original, ou a comparação destrói justamente o que está sendo verificado.
- Tempo-alvo
- O(n log n)
- Espaço-alvo
- O(n)
Solução
A fila alvo é só a entrada ordenada, então a tarefa toda é gerar essa cópia e comparar posição por posição. Ordenar uma cópia, e não a própria entrada, faz diferença: ordenar in-place sobrescreveria a fila que está sendo avaliada, e a contagem daria sempre zero. Comparar alturas, e não alunos, é suficiente, porque dois alunos da mesma altura são intercambiáveis e uma posição com a altura certa está correta, seja quem for que esteja ali. O tempo é O(n log n) pela ordenação, e o espaço é O(n) pela cópia.
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])) # -> 0Travou na ideia, e não no código? O básico de ordenação explica isso.