Longest Consecutive Sequence

Q: Qual é a complexidade de tempo da sequência consecutiva mais longa?

A solução com conjunto hash tem tempo de execução médio de O(n) e usa memória extra de O(n) . Ordenar e depois contar as sequências leva O(n log n) de tempo. Pesquisar no array cada próximo valor sem um conjunto leva até O(n³) .

Q: O union-find consegue resolver a Longest Consecutive Sequence?

Sim. Transforme cada valor distinto em um conjunto, una x a x+1 sempre que ambos estiverem presentes e retorne o tamanho do maior conjunto. O algoritmo é executado em tempo próximo de O(n) , mas precisa de um mapeamento de valores para índices, links para os pais e tamanhos, enquanto a iteração com conjunto hash faz o mesmo trabalho com um conjunto e dois loops.

MédioHashing

+10

Você recebe um array de números inteiros nums em nenhuma ordem específica. Uma sequência consecutiva é um grupo de valores x, x+1, x+2 e assim por diante, cada um aparecendo em algum lugar de nums. Retorne o comprimento da sequência consecutiva mais longa. Um valor que aparece mais de uma vez conta apenas uma vez.

Função

longestConsecutive(nums: integer-array) → integer

numsinteger-array: os números inteiros, em qualquer ordem, com repetições permitidas
Retornainteger: o comprimento da maior sequência de valores consecutivos presente em nums

Restrições

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Os valores podem se repetir. As posições no array não importam, apenas quais valores estão presentes.

Exemplos

Entrada: nums = [40, 4, 39, 1, 3, 2, 41]
Saída: 4
Explicação: 1, 2, 3 e 4 estão todos presentes, uma sequência de 4, embora estejam espalhados pelo array. A outra sequência, de 39 a 41, tem apenas 3 valores.

Entrada: nums = [7, 3, 7, 5, 6, 5]
Saída: 3
Explicação: 5, 6 e 7 formam uma sequência de 3. O segundo 7 e o segundo 5 não acrescentam nada, e 3 não pode se juntar porque 4 está faltando.

+17 testes ocultos ao enviar

Para ir além

Suponha que os valores cheguem um de cada vez e que, após cada um, você precise informar a sequência mais longa até então. Você consegue manter a resposta atualizada em tempo médio O(1) por valor?

Dicas

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

0 de 3 abertas

Solução

Os valores de uma sequência podem estar em qualquer lugar do array, então você não pode percorrer as sequências da esquerda para a direita. A ordenação os alinha em O(n log n). Um conjunto hash é melhor: ele responde à pergunta "há x+1 aqui?" em O(1) e, se você contar apenas a partir dos valores cujo x-1 está ausente, cada valor é percorrido uma vez, o que torna a busca inteira O(n).

Conte progressivamente a partir de cada valor ao pesquisar o array

Correta, mas não termina nos maiores testes

Intuição

Considere cada valor como um possível início de uma sequência. A partir de x, procure x+1 no array; se estiver lá, procure x+2 e continue até que falte um valor. A quantidade de valores alcançados é o tamanho da sequência que começa em x, e o maior desses tamanhos é a resposta.

Isso está correto porque toda sequência tem um menor valor, esse valor está em nums, e o loop o testa como início e percorre toda a sequência. Repetições não fazem mal: elas apenas testam o mesmo início duas vezes.

É lento por dois motivos. Cada verificação de “está aqui?” lê até n valores, e uma sequência longa é percorrida novamente a partir de cada um de seus elementos. Considere 10^4 valores que formam uma única sequência embaralhada: as caminhadas somam cerca de n²/2 = 5 × 10^7 etapas, e cada etapa percorre, em média, metade do array. Isso dá cerca de 2.5 × 10^11 comparações.

Algoritmo

Defina best como 0.
Para cada valor start em nums, defina current como start e length como 1.
Enquanto uma varredura de nums encontrar current+1, some 1 a current e a length.
Armazene length em best se for maior.
Retorne best.

def longestConsecutive(nums):
    best = 0
    for start in nums:
        current = start
        length = 1
        # "in" on a list reads it from the front until it finds the value.
        while current + 1 in nums:
            current += 1
            length += 1
        best = max(best, length)
    return best

Ordene e, em seguida, conte as sequências

Intuição

A ordenação coloca os valores de cada sequência uns ao lado dos outros. [40, 4, 39, 1, 3, 2, 41] se torna [1, 2, 3, 4, 39, 40, 41], e as sequências são lidas da esquerda para a direita: 1 a 4, depois um salto para 39.

Percorra os valores ordenados e mantenha o comprimento da sequência atual. Um valor uma unidade maior que o anterior estende a sequência. Um valor igual ao anterior é uma repetição: ignore-o, pois ele não estende nem encerra a sequência. Qualquer outro valor é uma lacuna, e uma nova sequência de comprimento 1 começa ali.

A ordenação custa O(n log n) e a varredura, O(n). Ordenar no próprio lugar não exige um array extra, mas reordena a entrada de quem chamou; linguagens que ordenam uma cópia usam O(n) de memória.

Algoritmo

Ordene nums em ordem crescente.
Defina best e run como 1, pois o array nunca está vazio.
Para cada índice i, começando em 1, ignore nums[i] se ele for igual a nums[i-1].
Se nums[i] for nums[i-1]+1, adicione 1 a run; caso contrário, defina run como 1. Armazene run em best se ele for maior.
Retorne best.

def longestConsecutive(nums):
    nums.sort()
    best = 1
    run = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            continue  # a repeat neither extends nor breaks the run
        if nums[i] == nums[i - 1] + 1:
            run += 1
        else:
            run = 1
        best = max(best, run)
    return best

Conjunto de hash, contando apenas a partir do início de cada execução

Intuição

Coloque cada valor em um conjunto hash. Agora, a pergunta " x+1 está presente?" custa O(1) em média, em vez de exigir uma busca, e as repetições são reduzidas a uma única entrada.

Percorrer a partir de cada valor ainda repetiria trabalho: na sequência 1, 2, 3, 4, você daria 3 passos a partir de 1, 2 a partir de 2 e 1 a partir de 3. Portanto, comece uma busca apenas no primeiro valor de uma sequência. Um valor x é o primeiro exatamente quando x-1 não está no conjunto. Em [40, 4, 39, 1, 3, 2, 41], apenas 1 e 39 se qualificam: a partir de 1, você chega a 4, um comprimento de 4, e a partir de 39, chega a 41, um comprimento de 3.

Cada valor pertence a exatamente uma sequência, e apenas a busca iniciada no primeiro valor dessa sequência passa por ele; assim, todas as buscas juntas dão no máximo n passos. Some uma verificação de pertencimento por valor e a criação do conjunto, e o total é O(n) de tempo, com O(n) de memória para o conjunto.

Faça o loop pelo conjunto, não por nums. Se o primeiro valor de uma sequência de 2.500 valores aparecer 2.000 vezes em nums, fazer o loop por nums percorrerá essa sequência 2.000 vezes.

Algoritmo

Coloque cada valor de nums em um conjunto hash values e defina best como 0.
Para cada valor x no conjunto, ignore-o se x-1 estiver no conjunto: ele não é o primeiro valor da sequência.
Caso contrário, defina end como x e incremente-o em 1 enquanto end+1 estiver no conjunto.
Armazene end-x+1 em best se for maior.
Retorne best.

def longestConsecutive(nums):
    values = set(nums)
    best = 0
    for value in values:
        # Only a value with no left neighbour starts a run.
        if value - 1 in values:
            continue
        end = value
        while end + 1 in values:
            end += 1
        best = max(best, end - value + 1)
    return best

Armadilhas e casos extremos

A maioria das respostas erradas vem de valores repetidos, e a maioria das respostas lentas, de percorrer o mesmo trecho mais de uma vez.

Tratar uma repetição como uma lacuna ou como um passo após a ordenação. Em [1, 2, 2, 3], reiniciar o trecho na segunda ocorrência de 2 resulta em 2, e contá-la como um passo resulta em 4. A resposta é 3.
Iniciar best em 0 na varredura ordenada e atualizá-lo somente dentro do loop. Nesse caso, um array com um único valor retorna 0 em vez de 1.
Percorrer cada valor do conjunto em vez de começar apenas no início dos trechos. A resposta está correta, mas um trecho de 10^4 valores custa 5 × 10^7 passos, o trabalho quadrático que o conjunto deveria eliminar.
Percorrer nums em vez do conjunto quando há valores repetidos. O trecho que começa em um valor que aparece milhares de vezes é percorrido milhares de vezes.
Marcar valores em um array indexado pelo valor. Os valores chegam a ±10^9, então o array precisaria de 2 × 10^9 posições.

Perguntas frequentes4

Qual é a complexidade de tempo da sequência consecutiva mais longa?

A solução com conjunto hash tem tempo de execução médio de O(n) e usa memória extra de O(n). Ordenar e depois contar as sequências leva O(n log n) de tempo. Pesquisar no array cada próximo valor sem um conjunto leva até O(n³).

Por que a solução com conjunto hash tem complexidade O(n) quando há um loop while dentro de um loop for?

O loop interno só é executado a partir de um valor cujo vizinho à esquerda x-1 está ausente, ou seja, o primeiro valor de sua sequência. Cada valor é percorrido pela caminhada de sua própria sequência e por nenhuma outra, portanto todos os loops internos juntos dão, no máximo, n passos. O loop externo acrescenta uma verificação por valor, totalizando O(n).

Você consegue resolver a sequência consecutiva mais longa sem memória extra?

Sim, se você puder reordenar a entrada: ordene-a no próprio lugar e conte as sequências em uma única passagem, ignorando as repetições. Isso usa memória extra O(1), mas leva tempo O(n log n). A solução O(n) precisa do conjunto hash.

O union-find consegue resolver a Longest Consecutive Sequence?

Sim. Transforme cada valor distinto em um conjunto, una x a x+1 sempre que ambos estiverem presentes e retorne o tamanho do maior conjunto. O algoritmo é executado em tempo próximo de O(n), mas precisa de um mapeamento de valores para índices, links para os pais e tamanhos, enquanto a iteração com conjunto hash faz o mesmo trabalho com um conjunto e dois loops.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [40, 4, 39, 1, 3, 2, 41]

Esperado

Longest Consecutive Sequence

Função

Restrições

Exemplos

Dicas

Solução

Conte progressivamente a partir de cada valor ao pesquisar o array

Ordene e, em seguida, conte as sequências

Conjunto de hash, contando apenas a partir do início de cada execução

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos