Intersection of Two Arrays

Q: Qual é a complexidade de tempo da interseção de dois arrays?

Com um conjunto hash, encontrar os valores em comum leva O(n + m) em média, e ordenar os k valores da resposta acrescenta O(k log k) ; o conjunto usa espaço O(n) . Ordenar os dois arrays e percorrê-los com dois ponteiros leva O(n log n + m log m) . Comparar cada par leva O(n × m) .

FácilHashing

+10

Você recebe dois arrays de números inteiros, nums1 e nums2. Retorne todos os valores que aparecem nos dois arrays, em ordem crescente. Cada valor em comum aparece uma vez na resposta, independentemente de quantas vezes ele se repete em qualquer um dos arrays.

Função

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

nums1integer-array: a primeira lista de números inteiros
nums2integer-array: a segunda lista de números inteiros
Retornainteger-array: os valores encontrados em ambas as listas, uma vez cada, em ordem crescente

Restrições

1 ≤ nums1.length, nums2.length ≤ 5000
-10⁵ ≤ nums1[i], nums2[i] ≤ 10⁵
Pelo menos um valor aparece em ambos os arrays.

Exemplos

Entrada: nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
Saída: [4, 6]
Explicação: 4 e 6 estão em ambos os arrays. 4 aparece duas vezes em nums2, mas é listado uma vez, e 2 e 9 nunca aparecem em nums2.

Entrada: nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
Saída: [-3, 7]
Explicação: -3 e 7 estão em ambos os arrays. Em ordem crescente, -3 vem primeiro, embora 7 venha primeiro em nums2.

+16 testes ocultos ao enviar

Para ir além

E se nums1 tiver 10 valores e nums2 tiver um milhão, já ordenados? Qual abordagem você escolheria, e a busca binária consegue ser mais rápida do que percorrer tudo?

Dicas

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

0 de 3 abertas

Solução

Dois detalhes determinam este problema: um valor que se repete nos dois lados entra apenas uma vez na resposta, e a resposta deve vir ordenada. Comparar cada par funciona, mas custa n × m comparações, 2.5 × 10^7 quando os dois arrays contêm 5000 valores. Ordenar os dois arrays permite que dois ponteiros encontrem os valores em comum em ordem, e um conjunto hash de um dos arrays responde à pergunta "este valor está em nums1?" em tempo constante.

Compare cada par

Correta, mas não termina nos maiores testes

Intuição

Pegue cada valor de nums1 e percorra nums2 em busca dele. Pare a busca na primeira correspondência e ignore um valor que já esteja na resposta, de modo que [8, 8, 8, 8] comparado com [8, 8] resulte em um único 8, não quatro. Ordene a resposta no final.

Está correto porque um valor entra na resposta exatamente quando alguma ocorrência dele em nums1 encontra uma correspondência em nums2, e o critério para ignorá-lo impede que ele entre duas vezes.

É lento porque cada valor de nums1 pode percorrer todo nums2. Com 5000 valores em cada array, isso representa até 2.5 × 10^7 comparações e, nos testes grandes, a maioria dos valores não encontra correspondência, então a maioria das buscas vai até o fim.

Algoritmo

Comece com uma lista de respostas vazia.
Para cada valor a em nums1, ignore-o se ele já estiver na resposta.
Caso contrário, percorra nums2; no primeiro valor igual a a, adicione a à resposta e interrompa a busca.
Ordene a resposta em ordem crescente e retorne-a.

def intersection(nums1, nums2):
    result = []
    for a in nums1:
        if a in result:
            continue
        # Look for a anywhere in nums2.
        for b in nums2:
            if a == b:
                result.append(a)
                break
    result.sort()
    return result

Ordene ambos e, em seguida, percorra com dois ponteiros

Intuição

Ordenado, o exemplo 1 se torna [2, 2, 4, 6, 9] e [1, 4, 4, 6]. Coloque o ponteiro i no início do primeiro array e j no início do segundo. O ponteiro no valor menor avança: esse valor não pode corresponder a nenhum valor mais adiante no outro array, onde todos os valores são pelo menos tão grandes. Quando os dois ponteiros veem o mesmo valor, ele é compartilhado, então adicione-o e avance ambos.

No exemplo: 2 > 1 move j, os dois valores 2 são menores que 4 e movem i, 4 = 4 adiciona 4, o segundo 4 é menor que 6 e move j, e 6 = 6 adiciona 6. Um valor compartilhado várias vezes em ambos os lados, como 2 em [2, 2, 3] e [2, 2], corresponde mais de uma vez; compará-lo com o último valor adicionado mantém uma cópia. O resultado já fica ordenado, sem nenhuma etapa extra.

A ordenação custa O(n log n + m log m), e o percurso é O(n + m) porque cada etapa move pelo menos um ponteiro. A maioria das versões ordena cópias, o que custa O(n + m) de memória. Se você puder reordenar as entradas, ordene-as no próprio lugar, como o código C faz, e a única memória extra será a da resposta.

Algoritmo

Ordene os dois arrays.
Defina i = 0 e j = 0.
Enquanto os dois ponteiros estiverem dentro dos arrays, mova o ponteiro que aponta para o menor valor.
Em valores iguais, adicione o valor, a menos que ele seja igual ao último valor adicionado; depois, mova os dois ponteiros.
Retorne a resposta.

def intersection(nums1, nums2):
    a = sorted(nums1)
    b = sorted(nums2)
    i, j = 0, 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            # A shared value: keep it once, even if it repeats.
            if not result or result[-1] != a[i]:
                result.append(a[i])
            i += 1
            j += 1
    return result

Conjunto hash do primeiro array

Intuição

Coloque cada valor de nums1 em um conjunto hash. No exemplo 1, o conjunto é {6, 2, 9, 4}: o 2 repetido é eliminado ao ser inserido. Em seguida, percorra nums2 e consulte o conjunto sobre cada valor em tempo constante. O primeiro 4 está lá, então ele vai para a resposta. O segundo 4 não deve ir, então você remove um valor do conjunto assim que ele corresponde. 1 não está lá, e 6 está, o que resulta em [4, 6].

Remover um valor quando há correspondência é o que garante que cada valor apareça uma única vez: depois da primeira correspondência, o valor sai do conjunto, então cópias posteriores em nums2 não encontram nada. Todo valor adicionado está nos dois arrays, e todo valor em comum é adicionado quando sua primeira cópia em nums2 aparece.

A construção do conjunto e a percorrida levam O(n + m) em média. A resposta sai na ordem de nums2, então ordene-a no final; ela contém k ≤ min(n, m) valores, o que custa O(k log k). C não tem um conjunto integrado, então o código em C usa um array de sinalizadores indexado por value + 10^5, que funciona porque os valores têm limites definidos.

Algoritmo

Crie um conjunto hash first a partir de nums1.
Para cada valor em nums2, se ele estiver em first, adicione-o à resposta e remova-o de first.
Ordene a resposta em ordem crescente.
Retorne-a.

def intersection(nums1, nums2):
    first = set(nums1)
    result = []
    for num in nums2:
        if num in first:
            result.append(num)
            # Remove it so a repeat in nums2 is not added twice.
            first.remove(num)
    result.sort()
    return result

Armadilhas e casos extremos

A maioria das respostas incorretas aqui se deve a valores repetidos e à ordem da saída.

Adicionar um valor sempre que ele corresponder. [2, 2, 3, 3, 3] e [3, 2, 2] têm dois valores em comum, então a resposta é [2, 3], não [3, 2, 2].
Retornar os valores na ordem em que você os encontrou. A iteração pelo conjunto hash percorre nums2, então [7, -3] ainda precisa ser ordenado para ficar como [-3, 7].
Ordenar números como texto. O sort() do JavaScript, sem um comparador, compara strings, então [100000, 99] permanece nessa ordem. Passe (x, y) => x - y.
Usar a interseção de conjuntos e esquecer a ordem. set(nums1) & set(nums2) do Python encontra os valores corretos sem uma ordem específica; envolva-o em sorted.
Indexar um array de sinalizadores pelo valor bruto. -3 não é um índice válido; primeiro, some 10^5 a cada valor.

Perguntas frequentes4

Qual é a complexidade de tempo da interseção de dois arrays?

Com um conjunto hash, encontrar os valores em comum leva O(n + m) em média, e ordenar os k valores da resposta acrescenta O(k log k); o conjunto usa espaço O(n). Ordenar os dois arrays e percorrê-los com dois ponteiros leva O(n log n + m log m). Comparar cada par leva O(n × m).

Você deve usar um conjunto hash ou dois ponteiros?

Use o conjunto hash quando os arrays não estiverem ordenados e houver memória disponível: ele exige menos trabalho. Use dois ponteiros quando os dois arrays já estiverem ordenados ou quando a memória for limitada e você puder ordená-los no próprio lugar. A varredura não precisa de conjunto e produz a resposta em ordem.

Como manter os valores repetidos na interseção?

Se um valor deve aparecer tantas vezes quanto ocorre em ambos os arrays, de modo que [3, 1, 3, 3] e [3, 3] resultem em [3, 3], substitua o conjunto por um mapa de contagens. Conte os valores de nums1 e, para cada valor de nums2 cuja contagem seja maior que zero, adicione-o e diminua sua contagem. Na iteração com dois ponteiros, remova a verificação em relação ao último valor adicionado.

Como encontrar a interseção quando um dos arrays é grande demais para caber na memória?

Crie o conjunto hash a partir do array que couber e leia o maior em partes, verificando cada valor no conjunto e removendo-o quando houver uma correspondência. O uso de memória permanece do tamanho do array menor. Se nenhum dos arrays couber, ordene ambos no disco e percorra os arquivos ordenados usando dois ponteiros.

Python

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

Casos de teste

Caso 1

Caso 2

Entrada

nums1 = [6, 2, 9, 2, 4]
nums2 = [4, 4, 1, 6]

Esperado

[4, 6]

Intersection of Two Arrays

Função

Restrições

Exemplos

Dicas

Solução

Compare cada par

Ordene ambos e, em seguida, percorra com dois ponteiros

Conjunto hash do primeiro array

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos