Merge Sorted Array

Q: Qual é a complexidade de tempo de mesclar dois arrays ordenados?

Com dois ponteiros, é O(m + n) , em que m e n são os dois comprimentos. A cada etapa, um valor é inserido, e nenhum valor é examinado duas vezes. Concatenar e ordenar custa O((m + n) log(m + n)) .

Q: Como mesclar dois arrays ordenados no próprio lugar?

Quando o primeiro array tiver espaço para ambos no final, preencha-o de trás para a frente. Compare os maiores valores restantes dos dois arrays, escreva o maior deles na última posição livre e avance uma posição para a esquerda. Escrever de trás para a frente nunca sobrescreve um valor do primeiro array que ainda não foi colocado, então não é necessário um segundo array.

Q: Mesclar dois arrays ordenados é a mesma coisa que a etapa de intercalação do merge sort?

Sim. O merge sort divide um array ao meio, ordena cada metade e, em seguida, junta as duas metades ordenadas exatamente com este loop de dois ponteiros. Escolher o valor da esquerda em caso de empate mantém os valores iguais na ordem original, o que torna o merge sort estável.

Q: Por que não concatenar os arrays e chamar sort?

Ele dá a resposta certa e, na prática, costuma ser rápido. Mas ignora que as entradas já estão ordenadas e custa um fator extra de log . Em uma entrevista, a mesclagem com dois ponteiros é a resposta esperada, porque mostra que você sabe aproveitar a ordenação fornecida.

FácilDois ponteiros Ordenação

+10

Você recebe dois arrays de números inteiros, nums1 e nums2. Cada um já está ordenado em ordem não decrescente. Retorne um único array que contenha todos os valores de ambos, também em ordem não decrescente. Um valor que aparece nos dois arrays aparece no resultado tantas vezes quanto aparece no total.

Função

merge(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: o primeiro array ordenado
nums2integer-array: o segundo array ordenado
Retornainteger-array: todos os valores de ambos os arrays em um único array ordenado, de comprimento nums1.length + nums2.length

Restrições

1 ≤ nums1.length, nums2.length ≤ 2000
-10⁵ ≤ nums1[i], nums2[j] ≤ 10⁵
nums1 e nums2 estão ordenados em ordem não decrescente.

Exemplos

Entrada: nums1 = [1, 4, 9]nums2 = [2, 3, 10]
Saída: [1, 2, 3, 4, 9, 10]
Explicação: Leia os dois primeiros elementos e mantenha o menor: 1, depois 2 e 3 de nums2, depois 4 e 9 de nums1, e 10 por último. O resultado contém os seis valores.

Entrada: nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
Saída: [-5, 0, 0, 0, 6, 8]
Explicação: O 0 aparece duas vezes em nums1 e uma vez em nums2, então o resultado tem três 0s. O -5 é menor que todos os elementos de nums2 e vem primeiro.

+13 testes ocultos ao enviar

Para ir além

Você consegue mesclar k arrays ordenados, contendo N valores no total, em O(N log k) de tempo?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Juntar os arrays e ordená-los fornece a resposta correta, mas isso ignora o fato de que as duas metades já estão ordenadas. O menor valor restante no total está sempre no início de um dos dois arrays. Mantenha um índice para cada array, pegue o menor valor do início a cada etapa, e uma única passagem constrói o resultado. Esta é a etapa de intercalação do merge sort.

Concatenar e ordenar

Intuição

Coloque cada valor de nums1 e cada valor de nums2 em um único array e, em seguida, ordene-o. O resultado contém os valores corretos, cada um aparecendo tantas vezes quanto aparecia, na ordem correta.

Para [1, 4, 9] e [2, 3, 10], o array combinado é [1, 4, 9, 2, 3, 10], e a ordenação resulta em [1, 2, 3, 4, 9, 10].

Com m valores em nums1 e n em nums2, uma ordenação geral custa O((m + n) log(m + n)). Ela funciona e é rápida o suficiente para esses limites, mas não aproveita a ordem já ordenada que foi fornecida. A próxima abordagem aproveita essa ordem e elimina o fator log.

Algoritmo

Crie um array com os valores de nums1 seguidos pelos de nums2.
Ordene-o em ordem numérica crescente.
Retorne-o.

def merge(nums1, nums2):
    return sorted(nums1 + nums2)

Dois ponteiros, um por array

Intuição

Mantenha um índice i em nums1 e j em nums2, ambos começando em 0. Tudo o que está antes de i e antes de j já está no resultado. O menor valor ainda não usado é nums1[i] ou nums2[j], porque cada array está ordenado e seus valores restantes só podem ser maiores. Acrescente o menor deles e avance esse índice.

Com [1, 4, 9] e [2, 3, 10]: 1 vence 2, depois 2 vence 4, 3 vence 4, 4 vence 10 e 9 vence 10. Agora, nums1 foi todo usado, então o restante de nums2, que é [10], é copiado como está. O resultado é [1, 2, 3, 4, 9, 10].

Cada etapa grava um valor, então o loop executa m + n vezes: tempo O(m + n). O array de resultado é a única memória extra.

Algoritmo

Defina i e j como 0 e crie um resultado vazio.
Enquanto ainda houver valores em ambos os arrays, compare nums1[i] com nums2[j].
Acrescente o menor e avance seu índice. Em caso de empate, escolha nums1[i].
Quando um array acabar, acrescente o que restar do outro.
Retorne o resultado.

def merge(nums1, nums2):
    result = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    # one array is used up; the rest of the other is already sorted
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    return result

Armadilhas e casos extremos

A maioria dos bugs aparece quando um dos arrays chega ao fim ou na forma como os valores são comparados.

Interromper o loop assim que um dos arrays acabar e esquecer o restante do outro. Com [1, 2, 3] e [4, 5, 6], o loop termina depois de 1, 2 e 3, e ainda é preciso copiar 4, 5, 6.
Ler nums1[i] depois que i chegou ao fim. Verifique os dois índices antes de comparar.
Descartar duplicatas. [0, 0] e [0] são mesclados em [0, 0, 0], não em [0].
Em JavaScript e TypeScript, sort() sem comparador ordena números como texto, então [-5, 10, 9] é ordenado como [-5, 10, 9]. Passe (a, b) => a - b.
Em Lua e R, os arrays começam em 1, então ambos os índices começam em 1 e os limites usam <=.

Perguntas frequentes4

Qual é a complexidade de tempo de mesclar dois arrays ordenados?

Com dois ponteiros, é O(m + n), em que m e n são os dois comprimentos. A cada etapa, um valor é inserido, e nenhum valor é examinado duas vezes. Concatenar e ordenar custa O((m + n) log(m + n)).

Como mesclar dois arrays ordenados no próprio lugar?

Quando o primeiro array tiver espaço para ambos no final, preencha-o de trás para a frente. Compare os maiores valores restantes dos dois arrays, escreva o maior deles na última posição livre e avance uma posição para a esquerda. Escrever de trás para a frente nunca sobrescreve um valor do primeiro array que ainda não foi colocado, então não é necessário um segundo array.

Mesclar dois arrays ordenados é a mesma coisa que a etapa de intercalação do merge sort?

Sim. O merge sort divide um array ao meio, ordena cada metade e, em seguida, junta as duas metades ordenadas exatamente com este loop de dois ponteiros. Escolher o valor da esquerda em caso de empate mantém os valores iguais na ordem original, o que torna o merge sort estável.

Por que não concatenar os arrays e chamar sort?

Ele dá a resposta certa e, na prática, costuma ser rápido. Mas ignora que as entradas já estão ordenadas e custa um fator extra de log. Em uma entrevista, a mesclagem com dois ponteiros é a resposta esperada, porque mostra que você sabe aproveitar a ordenação fornecida.

Python

def merge(nums1, nums2):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums1 = [1, 4, 9]
nums2 = [2, 3, 10]

Esperado

[1, 2, 3, 4, 9, 10]