Longest Consecutive Sequence
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 dos quais aparece em algum lugar de nums. Retorne o comprimento da maior sequência consecutiva. Um valor que aparece mais de uma vez conta apenas uma vez.
Função
- numsinteger-array
- os números inteiros, em qualquer ordem, repetições permitidas
- Retornainteger
- o comprimento da maior sequência de valores consecutivos presente em nums
Restrições
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- 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,3e4estão todos presentes, uma sequência de 4, embora estejam espalhados pelo array. A outra sequência, de39a41, tem apenas 3 valores.
- Entrada
- nums = [7, 3, 7, 5, 6, 5]
- Saída
- 3
- Explicação
5,6e7formam uma sequência de 3. O segundo7e o segundo5não acrescentam nada, e3não pode se juntar porque4está faltando.
- Entrada
- nums = [10, 30, 20]
- Saída
- 1
- Explicação
- Não há dois valores que diferem por 1, então cada sequência contém um único valor e a resposta é 1.
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 contínua 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.
Experimente cada valor como o primeiro número de uma sequência e conte em ordem crescente. Qual pergunta você faz repetidamente e qual é o custo de cada resposta quando você procura por ele no array?
A pergunta é "
x+1está no array?". Um conjunto hash responde a isso em tempo constante, em média, e também elimina as repetições.Comece a contar apenas a partir de um valor
xcujox-1não esteja no conjunto. A partir daí, avance parax+1,x+2e assim por diante enquanto o conjunto contiver esses valores, e mantenha a caminhada mais longa. Cada valor será percorrido por apenas uma caminhada.
Solução
Os valores de uma sequência podem estar em qualquer posição do array. A ordenação os organiza em O(n log n). Um conjunto hash responde à pergunta "o x+1 está aqui?" em O(1), e, se você contar apenas a partir dos valores cujo x-1 está ausente, cada valor é percorrido uma vez: O(n) no total.
Conte a partir de cada valor pesquisando o array
Correta, mas não termina nos maiores testes
Intuição
Trate cada valor como um possível início de uma sequência. A partir de x, procure no array por x+1, depois por x+2, até que falte um valor, e mantenha a maior contagem. Toda sequência tem um menor valor em nums, e o loop percorre toda a sequência a partir dele.
Cada busca lê até n valores, e uma sequência longa é percorrida novamente a partir de cada elemento. Para 10^4 valores que formam uma única sequência embaralhada, as percorridas levam cerca de n²/2 = 5 × 10^7 etapas, cada uma percorrendo metade do array, em média: cerca de 2.5 × 10^11 comparações.
Algoritmo
- Defina
bestcomo 0. - Para cada valor
startemnums, definacurrentcomostartelengthcomo 1. - Enquanto uma varredura de
numsencontrarcurrent+1, some 1 acurrente alength. - Armazene
lengthembestse ele 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 bestOrdene e, em seguida, conte as sequências
Intuição
A ordenação coloca os valores de cada sequência um ao lado do outro: [40, 4, 39, 1, 3, 2, 41] se torna [1, 2, 3, 4, 39, 40, 41], e as sequências são identificadas da esquerda para a direita.
Percorra os valores ordenados e mantenha o comprimento da sequência atual. Um valor uma unidade maior que o anterior estende a sequência. Uma repetição não estende nem encerra a sequência, então ignore-a. Qualquer outro valor inicia uma nova sequência de comprimento 1.
A ordenação custa O(n log n) e a varredura, O(n). Ordenar no próprio array não exige memória extra; linguagens que ordenam uma cópia usam O(n) de memória.
Algoritmo
- Ordene
numsem ordem crescente. - Defina
besteruncomo 1, pois o array nunca está vazio. - Para cada índice
ia partir de 1, ignorenums[i]se ele for igual anums[i-1]. - Se
nums[i]fornums[i-1]+1, adicione 1 arun; caso contrário, definaruncomo 1. Armazenerunembestse 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 bestConjunto hash, contando apenas a partir do início de cada execução
Intuição
Com cada valor em um conjunto hash, uma verificação de pertencimento custa O(1) em média, 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, percorra apenas a partir do primeiro valor de uma sequência, que é exatamente um valor x cujo x-1 está ausente. No exemplo 1, apenas 1 e 39 se qualificam, formando sequências de 4 e 3.
Cada valor pertence a uma sequência e só é percorrido pela caminhada dessa sequência, então todas as caminhadas juntas dão no máximo n passos. Com uma verificação por valor, o total é de tempo O(n) e memória O(n) para o conjunto.
Algoritmo
- Coloque cada valor de
numsem um conjunto hashvaluese definabestcomo 0. - Para cada valor
xno conjunto, ignore-o sex-1estiver no conjunto: ele não é o primeiro valor da sequência. - Caso contrário, defina
endcomoxe some 1 a ele enquantoend+1estiver no conjunto. - Armazene
end-x+1embestse 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
- Tratar uma repetição como uma lacuna ou um passo após a ordenação. Em
[1, 2, 2, 3], reiniciar a sequência no segundo2resulta em 2, e contá-lo como um passo resulta em 4. A resposta é 3. - Começar
bestem 0 no percurso ordenado e atualizá-lo somente dentro do loop. Nesse caso, um array com um único valor retorna 0 em vez de 1. - Percorrer a partir de cada valor do conjunto, em vez de somente a partir do início de cada sequência. Uma sequência de
10^4valores custa então5 × 10^7passos. - Percorrer
numsem vez do conjunto. Se o primeiro valor de uma sequência de 2.500 aparecer 2.000 vezes, a sequência será percorrida 2.000 vezes. - Indexar um array pelo valor. Os valores chegam a
±10^9, então são necessárias2 × 10^9entradas.
Perguntas frequentes3
Qual é a complexidade de tempo da sequência consecutiva mais longa?
A solução com conjunto hash é executada em tempo O(n) em média, com memória extra O(n). A ordenação e a contagem levam O(n log n). Procurar no array cada próximo valor sem um conjunto leva até 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 O(1) de memória extra, mas leva O(n log n) de tempo. A solução O(n) precisa do conjunto hash.
O union-find consegue resolver a sequência consecutiva mais longa?
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 mapa de valores para índices, links para os pais e tamanhos, enquanto a varredura do conjunto hash precisa de apenas um conjunto.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def longestConsecutive(nums):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
nums = [40, 4, 39, 1, 3, 2, 41]
Saída Esperada
4