Find the Duplicate Number
Você recebe um array nums de n+1 inteiros, cada um entre 1 e n. Exatamente um valor aparece mais de uma vez, possivelmente muitas vezes, e você retorna esse valor.
Resolva sem alterar nums e usando apenas uma quantidade constante de memória extra.
Função
- numsinteger-array
- n+1 inteiros, cada um entre 1 e n
- Retornainteger
- o valor que aparece mais de uma vez
Restrições
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- Exatamente um valor aparece duas ou mais vezes; todos os outros valores aparecem no máximo uma vez.
Exemplos
- Entrada
- nums = [2, 5, 1, 3, 5, 4]
- Saída
- 5
- Explicação
- Aqui,
né 5, e 5 está nas posições 1 e 4, então a resposta é 5. Todos os outros valores de 1 a 5 aparecem uma vez.
- Entrada
- nums = [4, 2, 4, 1, 4]
- Saída
- 4
- Explicação
- 4 aparece três vezes, nas posições 0, 2 e 4, enquanto 3 não aparece nenhuma vez. Uma repetição pode substituir vários valores ausentes, então a resposta é 4.
+17 testes ocultos ao enviar
Para ir além
A busca binária nos valores mantém ambas as regras em tempo O(n log n). Você consegue mantê-las em tempo O(n)?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Todo valor está entre 1 e
n, e o array tem posições de 0 an. Portanto, todo valor também é uma posição válida. Comece na posição 0, salte para a posiçãonums[0], depois para a posição indicada por esse valor, e assim por diante. O que deve acontecer com esse percurso?A caminhada nunca para e tem apenas
n+1posições para visitar, então entra em um loop. A posição onde ela entra no loop é alcançada a partir de duas posições diferentes, e ambas têm essa posição como valor.Encontre a entrada do ciclo com dois ponteiros começando na posição 0: um avança uma vez por rodada, e o outro, duas vezes, até chegarem à mesma posição. Em seguida, volte um deles para 0 e mova ambos um salto por vez. Eles se encontram na entrada, que é a resposta.
Solução
Um conjunto hash ou uma ordenação encontra a repetição imediatamente, mas ambos violam as regras: o conjunto precisa de memória para cada valor, e a ordenação altera nums. A solução está nos números. Cada valor está entre 1 e n, então também é uma posição válida no array. Leia cada valor como um link para outra posição e, ao seguir os links a partir da posição 0, você sempre acaba em um ciclo cuja entrada é o duplicado. Os ponteiros rápido e lento de Floyd encontram essa entrada usando dois inteiros.
Compare cada par
Correta, mas não termina nos maiores testes
Intuição
O valor repetido aparece em pelo menos duas posições i < j. Compare cada posição com todas as posições posteriores; o primeiro par com valores iguais fornece a resposta. No primeiro exemplo, a posição 1 contém 5, e a busca a partir da posição 2 encontra outro 5 na posição 4.
Isso mantém as duas regras: nada é escrito e a única memória usada são dois contadores de loop. É lento porque compara pares. Com n+1 = 10,001 valores e as duas cópias perto do final, verifica cerca de 5 × 10^7 pares.
Algoritmo
- Para cada posição
i, de 0 até o final: - Para cada posição
japósi, comparenums[i]comnums[j]. - Retorne
nums[i]na primeira correspondência.
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeatBusca binária pelo valor
Intuição
Pesquise o intervalo de valores, não as posições. Escolha um limite m e conte quantas entradas de nums são menores ou iguais a m.
Se o duplicado d for maior que m, os valores de 1 a m aparecem no máximo uma vez cada, então a contagem é no máximo m. Se d for menor ou igual a m, todo valor acima de m aparece no máximo uma vez, então no máximo n-m entradas são maiores que m e pelo menos m+1 são menores ou iguais a m. Portanto, o teste "count > m" é falso para todo m abaixo de d e verdadeiro a partir de d. A busca binária encontra o primeiro m para o qual ele se torna verdadeiro, e esse valor é d.
No segundo exemplo, n é 4. Para m = 2, as entradas 2 e 1 resultam em uma contagem de 2, não maior que 2, então a resposta é maior que 2. Para m = 3, a contagem ainda é 2, então a resposta é 4. Cada rodada percorre o array inteiro uma vez e reduz o intervalo pela metade, então o trabalho é O(n log n): cerca de 14 passagens por 10,001 valores.
Algoritmo
- Defina
low= 1 ehigh=n, o comprimento denumsmenos um. - Enquanto
low < high, escolhamidno ponto médio entre eles. - Conte os elementos de
numsque são menores ou iguais amid. - Se a contagem for maior que
mid, definahigh=mid; caso contrário, definalow=mid+1. - Retorne
low.
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return lowDetecção de ciclo de Floyd nos links de valores
Intuição
Leia o array como links: a posição i aponta para a posição nums[i]. Cada posição de 0 a n tem exatamente um link de saída, e cada link chega a algum lugar entre 1 e n. No primeiro exemplo, os links são 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5 e 5 → 4.
Comece na posição 0 e siga os links. O percurso nunca pode parar, porque cada posição tem um link, e há apenas n+1 posições, então ele precisa voltar a uma posição que já visitou. A partir daí, seguirá em círculos para sempre. O caminho é uma cauda seguida por um ciclo, com o formato da letra ρ. No primeiro exemplo, o percurso é 0, 2, 1, 5, 4, 5, 4 e assim por diante: a cauda é 0, 2, 1 e o ciclo é 5, 4. A posição 3 aponta para si mesma, mas o percurso nunca chega até ela, e isso não causa problema.
A entrada do ciclo é o duplicado. O percurso entra em 5 duas vezes, vindo de posições diferentes: uma vez a partir do fim da cauda (posição 1, porque nums[1] é 5) e outra vez a partir do fim do ciclo (posição 4, porque nums[4] é 5). Duas posições diferentes contêm o valor 5, então 5 se repete. A cauda sempre contém a posição 0, porque nenhum valor é 0 e nada aponta de volta para ela, então a entrada sempre tem esses dois caminhos diferentes de chegada. Exatamente um valor se repete, portanto a entrada é esse valor.
Agora encontre a entrada com dois ponteiros, como na detecção de ciclos em listas encadeadas. Na fase 1, slow segue um link por rodada e fast segue dois, até ficarem na mesma posição em algum ponto do ciclo. No primeiro exemplo, eles se encontram em 4. Na fase 2, coloque slow de volta em 0, deixe fast onde está e avance ambos um link por rodada. Eles se encontram na entrada.
Por que a fase 2 funciona: suponha que a cauda tenha T links até chegar à entrada e que o ciclo tenha C posições. Quando os ponteiros se encontraram, slow tinha dado s passos e fast, 2s. Ambos estavam no mesmo ponto, então os s passos adicionais de fast correspondiam a voltas completas no ciclo. Após mais T passos, slow chega à entrada partindo de 0, e fast fica onde um percurso iniciado em 0 estaria após s+T passos, pois as voltas adicionais não mudam nada. Isso equivale a T passos até a entrada mais s passos, um número inteiro de voltas, o que também o coloca na entrada. Eles não podem se encontrar antes, porque slow ainda está na cauda e fast nunca sai do ciclo. No primeiro exemplo, slow percorre 2, 1, 5 enquanto fast percorre 5, 4, 5, e eles se encontram em 5 após T = 3 passos.
Cada fase leva O(n) passos, a única memória usada são duas posições, e nums nunca é modificado.
Algoritmo
- Considere cada posição
icomo um nó que aponta para a posiçãonums[i]e comece com os dois ponteiros na posição 0. - Fase 1: avance
slowparanums[slow]efastparanums[nums[fast]]até que sejam iguais. - Fase 2: defina
slownovamente como 0. - Avance ambos um elo por vez:
slowparanums[slow]efastparanums[fast], até que sejam iguais. - Retorne essa posição: ela é o valor repetido.
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Armadilhas e casos extremos
A maioria das respostas erradas surge ao confundir posições com valores ou ao interromper o método de Floyd uma fase antes do momento certo.
- Retornar o ponto de encontro da fase 1. Ele é uma posição qualquer no ciclo, não necessariamente a entrada. No primeiro exemplo, os ponteiros se encontram em 4, mas a resposta é 5.
- Verificar
slow == fastantes do primeiro movimento. Ambos começam em 0, então o loop termina imediatamente. Mova primeiro e depois compare, ou comece com eles uma e duas ligações à frente. - Começar a caminhada em qualquer posição diferente de 0. Nenhuma ligação aponta para a posição 0, já que nenhum valor é 0, e isso é o que garante uma cauda. Começar em outra posição pode colocar você em um ciclo sem caminho de entrada vindo de fora, como a posição 3 no primeiro exemplo, cuja entrada não prova nada.
- Presumir que o valor duplicado aparece exatamente duas vezes. O truque da soma, total menos
1 + 2 + ... + n, resulta em 15 menos 10 = 5 no segundo exemplo, mas a resposta é 4. O mesmo vale para os truques com XOR. - Fazer busca binária sobre posições em vez de valores, ou testar
count >= mid. A contagem de valores menores ou iguais amé exatamentemquando nenhum valor de 1 amse repete e nenhum está ausente, então apenas>distingue os dois lados. - Marcar os valores visitados negando
nums[x]ou trocando os valores de lugar. Ambos funcionam, mas ambos alteram o array, o que a tarefa proíbe.
Perguntas frequentes4
Qual é a complexidade de tempo de Encontrar o número duplicado?
A detecção de ciclos de Floyd é executada em O(n) com O(1) de memória extra: cada uma de suas duas fases percorre no máximo alguns múltiplos de n ligações. A busca binária nos valores leva O(n log n) e usa O(1) de memória. Comparar todos os pares é O(n²).
Por que a detecção de ciclo de Floyd encontra o número duplicado?
Se você ler cada valor como um link da posição em que está para a posição que ele nomeia, o percurso a partir da posição 0 deve terminar em um ciclo, porque nunca para e só há n+1 posições para percorrer. A posição em que ele entra no ciclo é alcançada a partir de duas posições diferentes, uma na cauda e outra no ciclo, então duas entradas contêm esse valor. O método de Floyd encontra a entrada de um ciclo com dois ponteiros, então encontra o valor repetido.
Por que não usar um conjunto hash ou ordenar o array?
Ambos encontram a resposta em tempo O(n) ou O(n log n), e em um programa real qualquer um deles serviria. A tarefa os proíbe de propósito: um conjunto hash usa memória extra O(n), e a ordenação altera nums ou exige uma cópia completa. São as restrições que levam você a considerar a perspectiva dos ciclos.
Por que a fórmula da soma não funciona para Encontrar o Número Duplicado?
Subtrair 1 + 2 + ... + n da soma do array dá o duplicado apenas quando ele aparece exatamente duas vezes e todos os outros valores aparecem uma vez. Aqui, a repetição pode aparecer muitas vezes e substituir valores ausentes. Em [4, 2, 4, 1, 4], a diferença é 15 menos 10 = 5, que nem sequer está no array.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def findDuplicate(nums):
# Escreva o código aquiCaso 1
Caso 2
Entrada
nums = [2, 5, 1, 3, 5, 4]
Esperado
5