Sort Colors

Q: O que é o problema da bandeira nacional holandesa?

Edsger Dijkstra propôs o seguinte problema: dados objetos de três cores em uma fila — o vermelho, o branco e o azul da bandeira holandesa —, agrupe cada cor em um único trecho, em uma só passagem, usando apenas trocas. Sort Colors é o mesmo problema com os números 0, 1 e 2. A solução dele é a partição com três ponteiros low , mid e high .

Q: Qual é a complexidade de tempo e espaço de Sort Colors?

A solução de uma única passagem é executada em tempo O(n), porque cada etapa reduz a parte não lida em uma célula. 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.

Q: Por que mid não se move depois de trocar de posição com high?

O valor que volta de high nunca foi lido, então pode ser 0, 1 ou 2. Avançar mid além dele deixaria um 0 ou um 2 no meio. Uma troca com low é diferente: tudo entre low e mid é 1, então o valor que volta é conhecido e mid pode avançar.

Q: O ordenamento por contagem é uma resposta aceitável para Ordenar Cores?

Ele atende aos limites de tempo O(n) e espaço O(1), e muitos entrevistadores o aceitam como uma primeira resposta. Espere a pergunta complementar sobre como fazer isso em uma única passagem, que é a partição com três ponteiros. A contagem é a melhor ferramenta quando há muitas cores, já que a partição divide apenas em três grupos.

MédioDois ponteiros Ordenação

+10

Você recebe um array nums em que cada valor é 0, 1 ou 2. Pense neles como três cores, por exemplo, 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. A ideia é usar o que você sabe sobre os valores.

Função

sortColors(nums: integer-array) → integer-array

numsinteger-array: as cores, cada uma 0, 1 ou 2
Retornainteger-array: os mesmos valores, primeiro todos os 0, depois todos os 1 e, em seguida, todos os 2

Restrições

1 ≤ nums.length ≤ 1.5 × 10⁴
Cada nums[i] é 0, 1 ou 2.
Uma cor pode estar faltando, 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.

+17 testes ocultos ao enviar

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.

0 de 3 abertas

Solução

Qualquer ordenação resulta na ordem correta, então a verdadeira questão é o que os três valores permitem que você dispense. Como só podem aparecer 0, 1 e 2, você pode contá-los e reescrever o array em duas passagens. Com três ponteiros que marcam onde terminam os 0s e onde começam os 2s, você pode até colocar cada valor em seu lugar em uma única passagem. Essa partição em uma passagem é o algoritmo da bandeira nacional holandesa.

Ordenação por bolha à mão

Correta, mas não termina nos maiores testes

Intuição

Uma ordenação de biblioteca seria executada em O(n log n), mas as regras do problema a proíbem, porque o entrevistador quer ver o que você faz sabendo que existem apenas três valores. A abordagem básica é, então, uma ordenação que você mesmo implementa, e a mais curta de acertar é a ordenação por bolhas: percorra o array e, sempre que dois elementos vizinhos estiverem fora de ordem, troque-os.

Uma passagem leva o maior valor que encontra até o final, como uma bolha subindo. Após a primeira passagem, a última posição está definida; após a segunda, as duas últimas estão, então n-1 passagens deixam o array inteiro em ordem. Em [2, 1, 0], a primeira passagem leva o 2 até o final, resultando em [1, 0, 2], e a segunda passagem troca o 1 e o 0.

Ela é lenta porque cada passagem compara todos os pares que ainda não estão na posição final: cerca de n²/2 comparações no total. Com n = 1.5 × 10^4, isso representa mais de 10^8 comparações, além de uma troca para cada par que começa fora de ordem, e nenhum desse trabalho 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] e nums[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 últimas done + 1 posiçõ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 nums

Conte cada cor e, em seguida, reescreva

Intuição

O bubble sort passa todo o tempo comparando elementos vizinhos, mas você já sabe quais valores existem. Se o array tiver dois 0s, três 1s e dois 2s, a resposta já está definida antes de você mover qualquer coisa: dois 0s, três 1s e dois 2s. Só as contagens importam.

Então, leia o array uma vez e conte cada valor. Depois, sobrescreva-o desde o início: count[0] zeros, depois count[1] uns e, em seguida, count[2] dois. Isso é ordenação por contagem, e é segura aqui porque valores iguais são intercambiáveis. Um 1 é um 1, então não é necessário preservar nada da ordem original.

São duas passagens e três contadores, tempo O(n) e espaço O(1). Isso atende aos limites e é a resposta natural quando há muitas cores. A pergunta complementar pela qual esse problema é conhecido é se você consegue fazer isso lendo o array apenas uma vez.

Algoritmo

Crie três contadores, todos com valor 0.
Leia cada valor e adicione um ao seu contador.
Escreva count[0] zeros desde o início, depois count[1] uns e, então, 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 nums

Uma passagem com três ponteiros (bandeira nacional holandesa)

Intuição

Expanda três regiões enquanto lê: 0s no início, 1s depois deles, 2s no final e uma parte ainda não lida entre os 1s e os 2s. Três índices marcam as fronteiras. Tudo antes de low é 0, tudo de low até, mas sem incluir, mid é 1, tudo depois de high é 2, e nums[mid] até nums[high] ainda não foi lido.

Leia nums[mid]. Um 1 já está na região correta, então avance mid. Um 0 pertence ao início: troque-o com nums[low] e avance low e mid. O valor que retorna de low é um 1 (ou o mesmo 0, quando nenhum 1 foi encontrado ainda), então já está no lugar certo. Um 2 pertence ao final: troque-o com nums[high] e recue high, mas mantenha mid onde está, pois o valor que veio de high ainda não foi lido.

A cada etapa, mid avança ou high recua, então a parte ainda não lida perde uma posição a cada vez e o loop termina após n etapas. Acompanhe [2, 0, 2]: o primeiro 2 é trocado com o último 2 e high diminui para 1; o índice 0 ainda contém um 2, que é trocado com o 0 e high diminui para 0; o índice 0 agora contém o 0, que fica no lugar, e você obtém [0, 2, 2].

Algoritmo

Defina low = 0, mid = 0 e high como o último índice.
Enquanto mid ≤ high, leia nums[mid].
Se for 0, troque-o por nums[low] e mova low e mid uma posição para a direita.
Se for 1, mova mid uma posição para a direita.
Se for 2, troque-o por nums[high] e mova high uma posição para a esquerda. Mantenha mid no 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

A versão de passagem única é curta, e quase todos os bugs nela são causados por um ponteiro que se move quando não deveria.

Avançar mid depois de uma troca com high. 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 o loop enquanto mid < high quando high é o índice do último elemento ainda não lido. Quando os dois se encontram, essa posição ainda não foi lida. Em [1, 0], o loop para antes de ler o 0 e retorna [1, 0].
Deixar high ficar abaixo de zero usando um índice sem sinal. Um array contendo apenas 2s, como [2], faz high chegar a -1. Em Rust, onde os índices são usize, mantenha high uma posição além da parte ainda não lida, como faz o código em Rust.
Presumir que todas as cores aparecem. [2, 0, 2] não tem nenhum 1, e um array pode conter uma única cor. As regras dos ponteiros lidam com ambos os casos sem condições especiais, então não adicione nenhuma.

Perguntas frequentes4

O que é o problema da bandeira nacional holandesa?

Edsger Dijkstra propôs o seguinte problema: dados objetos de três cores em uma fila — o vermelho, o branco e o azul da bandeira holandesa —, agrupe cada cor em um único trecho, em uma só passagem, usando apenas trocas. Sort Colors é o mesmo problema com os números 0, 1 e 2. A solução dele é a partição com três ponteiros low, mid e high.

Qual é a complexidade de tempo e espaço de Sort Colors?

A solução de uma única passagem é executada em tempo O(n), porque cada etapa reduz a parte não lida em uma célula. 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.

Por que mid não se move depois de trocar de posição com high?

O valor que volta de high nunca foi lido, então pode ser 0, 1 ou 2. Avançar mid além dele deixaria um 0 ou um 2 no meio. Uma troca com low é diferente: tudo entre low e mid é 1, então o valor que volta é conhecido e mid pode avançar.

O ordenamento por contagem é uma resposta aceitável para Ordenar Cores?

Ele atende aos limites de tempo O(n) e espaço O(1), e muitos entrevistadores o aceitam como uma primeira resposta. Espere a pergunta complementar sobre como fazer isso em uma única passagem, que é a partição com três ponteiros. A contagem é a melhor ferramenta quando há muitas cores, já que a partição divide apenas em três grupos.

Python

def sortColors(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [2, 1, 0, 2, 0, 1, 1]

Esperado

[0, 0, 1, 1, 1, 2, 2]

Sort Colors

Função

Restrições

Exemplos

Dicas

Solução

Ordenação por bolha à mão

Conte cada cor e, em seguida, reescreva

Uma passagem com três ponteiros (bandeira nacional holandesa)

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos