Sort Colors
Você recebe um array nums em que cada valor é 0, 1 ou 2: três cores, como vermelho, branco e azul. Reorganize o array para que todos os 0s venham primeiro, depois todos os 1s e, em seguida, todos os 2s, e retorne-o. Resolva sem usar uma função de ordenação de biblioteca.
Função
- numsinteger-array
- as cores, cada uma com 0, 1 ou 2
- Retornainteger-array
- os mesmos valores, primeiro todos os 0, depois todos os 1 e, por fim, todos os 2
Restrições
1 ≤ nums.length ≤ 1.5 × 104- Cada
nums[i]é0,1ou2. - Uma cor pode estar ausente, e o array pode conter uma única cor.
Exemplos
- Entrada
- nums = [2, 1, 0, 2, 0, 1, 1]
- Saída
- [0, 0, 1, 1, 1, 2, 2]
- Explicação
- O array contém dois 0s, três 1s e dois 2s, então o resultado é exatamente esse: dois 0s, depois três 1s e, por fim, dois 2s.
- Entrada
- nums = [2, 0, 2]
- Saída
- [0, 2, 2]
- Explicação
- Não há nenhum 1. O único 0 vai para o início, e os dois 2s vêm em seguida.
- Entrada
- nums = [1]
- Saída
- [1]
- Explicação
- Um único valor já está em ordem, então o array permanece inalterado.
Para ir além
O que você mudaria se houvesse k cores em vez de três, com k muito menor que o comprimento do array?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Apenas três valores diferentes podem aparecer. O que isso permite fazer que uma ordenação geral não permite?
Contar os 0s, 1s e 2s e reescrever o array funciona em duas passagens. Para uma passagem, imagine três regiões crescendo ao mesmo tempo: 0s na frente, 2s atrás, 1s no meio.
Mantenha três índices:
low,midehigh. Leianums[mid]: um 0 é trocado comlow, um 2 é trocado comhigh, um 1 permanece. Após uma troca comhigh, leia a mesma posição novamente.
Solução
Apenas 0, 1 e 2 podem aparecer, então você pode contá-los e reescrever o array em duas passagens. Três ponteiros que marcam onde os 0s terminam e onde os 2s começam fazem isso em uma passagem, colocando cada valor em seu lugar enquanto você o lê. Essa partição é o algoritmo da bandeira nacional holandesa.
Ordenação por bolha à mão
Correta, mas não termina nos maiores testes
Intuição
Sem uma função de ordenação de biblioteca, a alternativa básica é uma ordenação que você mesmo escreve. A ordenação por bolha percorre o vetor e troca quaisquer dois elementos vizinhos que estejam fora de ordem. Cada passada leva o maior valor encontrado até o final, então, após n-1 passadas, todas as posições estão definidas.
Ela faz cerca de n²/2 comparações: mais de 10^8 para n = 1.5 × 10^4, e nenhuma delas aproveita o fato de que existem apenas três valores.
Algoritmo
- Execute n-1 passagens pelo array.
- Em cada passagem, compare cada par de vizinhos
nums[j]enums[j + 1]que ainda não esteja na posição final e troque-os quando o da esquerda for maior. - Após a passagem de número
done(contando a partir de 0), as últimasdone + 1posições contêm seus valores finais, então a próxima passagem para antes delas. - Retorne
nums.
def sortColors(nums):
n = len(nums)
for done in range(n - 1):
# One pass: the largest value left so far bubbles to index n-1-done.
for j in range(n - 1 - done):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return numsConte cada cor e depois reescreva
Intuição
Valores iguais são intercambiáveis, então apenas as contagens importam. No primeiro exemplo, dois 0s, três 1s e dois 2s determinam a resposta antes de você mover qualquer elemento.
Percorra o array uma vez para contar cada valor e, em seguida, sobrescreva-o desde o início: count[0] zeros, count[1] uns, count[2] dois. Isso é ordenação por contagem. Duas passagens e três contadores resultam em tempo O(n) e espaço O(1).
Algoritmo
- Crie três contadores, todos com valor 0.
- Leia cada valor e adicione um ao seu contador.
- Escreva
count[0]zeros no início, depoiscount[1]uns e, em seguida,count[2]dois. - Retorne
nums.
def sortColors(nums):
count = [0, 0, 0] # how many 0s, 1s and 2s
for x in nums:
count[x] += 1
i = 0
for color in range(3):
for _ in range(count[color]):
nums[i] = color
i += 1
return numsUma passagem com três ponteiros (bandeira nacional holandesa)
Intuição
Expanda três regiões enquanto lê. Tudo antes de low é 0, tudo de low até, mas sem incluir, mid é 1, tudo depois de high é 2, e de nums[mid] a nums[high] ainda não foi lido.
Leia nums[mid]. Um 1 já está em sua região, então avance mid. Um 0 troca de lugar com nums[low] e ambos avançam: o valor que volta de low é um 1, ou o mesmo 0 quando nenhum 1 foi encontrado ainda, então ele está no lugar certo. Um 2 troca de lugar com nums[high] e high recua, mas mid fica onde está, porque o valor que veio de high ainda não foi lido.
A cada passo, mid avança ou high recua, então o loop termina após n passos. Em [2, 0, 2], o primeiro 2 troca de lugar com o último e high diminui para 1; o índice 0 ainda contém um 2, que troca de lugar com o 0; então o 0 fica no lugar, resultando em [0, 2, 2].
Algoritmo
- Defina
low = 0,mid = 0ehighcomo o último índice. - Enquanto
mid ≤ high, leianums[mid]. - Se for 0, troque-o por
nums[low]e movalowemiduma posição à direita. - Se for 1, mova
miduma posição à direita. - Se for 2, troque-o por
nums[high]e movahighuma posição à esquerda. Mantenhamidno lugar. - Retorne
nums.
def sortColors(nums):
# nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
# The value swapped in from high is unread, so mid stays.
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
Armadilhas e casos extremos
- Avançar
midapós uma troca comhigh. O valor que chega ainda não foi lido: em[1, 2, 0], o 2 troca de lugar com o 0, e pular o 0 resulta em[1, 0, 2]. - Repetir enquanto
mid < high. Quando os dois se encontram, essa célula ainda não foi lida: em[1, 0], o loop para antes de ler o 0 e retorna[1, 0]. - Permitir que
highfique abaixo de zero com um índice sem sinal. Um vetor contendo apenas 2s, como[2], fazhighchegar a -1, o que causa underflow em umusizedo Rust. Em vez disso, mantenhahighuma posição além da parte ainda não lida.
Perguntas frequentes3
O que é o problema da bandeira nacional holandesa?
Edsger Dijkstra propôs o seguinte problema: organize objetos de três cores em uma fila — vermelho, branco e azul, as cores da bandeira dos Países Baixos — de modo que cada cor fique agrupada, em uma única passagem e usando apenas trocas. Sort Colors é o mesmo problema com 0, 1 e 2, e a solução dele é o particionamento com três ponteiros.
Qual é a complexidade de tempo e espaço de Sort Colors?
A solução de uma passagem é executada em tempo O(n), porque cada etapa reduz em uma célula a parte não lida. Ela usa O(1) de espaço extra: três índices e um valor temporário para a troca. A ordenação por contagem tem os mesmos limites, mas lê o array duas vezes.
O counting sort é uma resposta aceitável para Sort Colors?
Ele atende aos limites de tempo O(n) e espaço O(1), e muitos entrevistadores o aceitam como uma primeira resposta. Espere que, em seguida, peçam uma única passagem. A contagem é a melhor ferramenta quando há muitas cores, já que a partição se divide em apenas três grupos.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def sortColors(nums):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
nums = [2, 1, 0, 2, 0, 1, 1]
Saída Esperada
[0, 0, 1, 1, 1, 2, 2]